首页 > 试题广场 >

改考卷

[编程题]改考卷
  • 热度指数：1166 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在上小学的时候，我们经常碰到这样的事:考完试后老师懒得改试卷，于是让我们同桌相互交换试卷后为对方批改。但是后来老师发现这样作容易出现作弊，于是他想了一个新办法。 老师将同学分成了 n 个组，其中编号为 𝑖 的组中有 𝑠𝑖 个人。然后老师会按某种顺序依次访问 这些组。 对于他访问的第一个组，他会将这组内的所有试卷都收走，放置在桌上;对于他后续访问的每一个组，首先他会从桌上的试卷最上方拿出该组对应人数数量的试卷，随机分配给该组每 个人一张试卷让他们进行批改，而后再将这组学生自己考的试卷收走放置在桌面试卷的最下方。当他访问完所有的组后他会将桌面上剩余的所有试卷随机分配给他第一个访问的组的学生进行批改。 但他发现这种方法有时候也会出现问题:有可能在中途访问到某个组的时候桌面上的试卷不够分配给这组学生每人一张;也有可能最后会有学生分配到批改自己的试卷，而且这两种情 况是否出现是与他访问每个组的顺序有关的。现在他想知道是否存在一种访问顺序能够使以 上两种情况都不出现，顺利完成试卷批改呢?

数据范围： ，

输入描述:
第一行包含一个整数𝑛，表示学生组数。
第二行包含𝑛个整数，𝑠1,𝑠2,...,𝑠𝑛，分别表示每组学生的人数。


输出描述:
若存在一种访问顺序能使试卷顺利批改完成，输出 Yes，否则输出 No。
示例1

输入

2
10 20

输出

No

说明

如果以 10 20 的顺序访问，则在第二组的时候作业不够第二组分，如果以 20 10 的顺序访问，则分给 20 人组的作业中有 10 本是本组的
示例2

输入

4
2 3 3 1

输出

Yes

说明

我们可以选择先访问人数为 3 的组，再访问人数为 3 的组，再访问人数
为 1 的组，最后访问人数为 2 的组。
算法知识视频讲解
添加回答
pein531头像 pein531
当访问到第i组的时候已经收走了试卷s1-s2+s2-s3+s3-s4+s4...-si-1+si-1=s1份（第一组收了s1第二组发了s2又收上来s2......），只要保证s1不小于si就能有充足的试卷发下来，为了保证试卷充足对任意的 i 成立，s1必须是最大值，也就是说必须第一个收走学生数量最多的那一组的试卷。
而老师是先收走第 i 组的试卷，然后再发其他组的试卷给第 i 组的同学批改，因此第 i 组是不可能改到自己的试卷的。只有可能是第一组从剩下的试卷中还能拿到本组同学的试卷，从而有可能改到自己的试卷。如果这种情况发生了，说明桌面最上方的s1张试卷访问了一圈还没被发完，需要第一组的同学自己来领，而此时已经发出去了s2+s3+...+sn张试卷，因此如果s1>s2+s3+...+sn就没办法完成试卷的顺利批改（即最大值大于其余项之和），存在自己改到自己试卷的可能性。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strS = br.readLine().trim().split(" ");
        int[] s = new int[n];
        int sum = 0, max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            s[i] = Integer.parseInt(strS[i]);
            sum += s[i];
            max = s[i] > max? s[i]: max;
        }
        if(max > sum - max) System.out.println("No");
        else System.out.println("Yes");
    }
}

发表于 2021-04-05 19:22:51 回复(0)
无心2019头像 无心2019 
#include <bits/stdc++.h>
using namespace std; 
int main()
{
    int n,i,j,sum=0,s[31];
    cin>>n;
    for(i=0;i<n;i++)
       cin>>s[i];
    sort(s,s+n);
    reverse(s,s+n);
    for(i=1;i<n;i++)
        sum=sum+s[i];
    if(s[0]<=sum)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

发表于 2019-06-16 20:11:08 回复(0)
Python
丶昕楚头像 丶昕楚
Python Code 
while True:
    try:
        n=int(input())
        M=sorted(list(map(int,input().split())),reverse=True)
        print('No' if M[0]>sum(M)/2 else 'Yes')
    except:
        break

发表于 2019-03-17 11:46:20 回复(0)
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        int sum = 0, max = 0;
        for (String s : br.readLine().split(" ")) {
            int num = Integer.parseInt(s);
            sum += num;
            if (num > max) max = num;
        }

        System.out.println(max > sum - max ? "No" : "Yes");
    }
}

发表于 2019-03-13 16:32:44 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int n,x,s=0,t=0;     cin>>n;     while(n--){         cin>>x;         s += x;         t = max(t,x);     }     cout<<((t>s/2)?"No":"Yes")<<endl;     return 0;
}

发表于 2019-02-06 02:17:45 回复(0)
Java
桉树叶AND薄荷叶头像 桉树叶AND薄荷叶
当访问第 i 组时，手上有的卷子数：s1-s2+s2-s3+s3...-s(i-1)+s(i-1)=s1；
为了保证第 i 组的同学够分，必须有 s1 >= si，即要将人数最多的作为第 1 组；
又因为除了第 1 组，后面每组都是先被分试卷，再被收自己的试卷，所以这些组的同学不会被分配到自己的试卷，因此只有第 1 组的同学可能会收到自己的试卷；
当最后访问第 1 组时，已经分发出的卷子数：s2+s3+...+sn；
若第 1 组收到了自己的试卷，说明压在最上面的 s1 还没有分完，即 s1>s2+s3+...+sn。
根据上面的思路就是：数组中最大值要大于其余值之和。
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] arr = br.readLine().trim().split(" ");
        int[] num = new int[arr.length];
        for(int i = 0; i < arr.length; i++) {
            num[i] = Integer.parseInt(arr[i]);
        }
        
        // 遍历找到最大值，也就是使 max >= si
        int p = 0;
        int sum = 0;    // 去掉最大值时的和
        for(int i = 1; i < num.length; i++) {
            if(num[i] > num[p]) {
                p = i;
            }
            sum += num[i];
        }
        sum = num[0] + sum - num[p];
        // 判断是否 max > sum
        if(num[p] > sum) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}


编辑于 2020-08-24 22:02:37 回复(0)
C++
牛客409434554号头像 牛客409434554号 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,maxn=INT_MIN,sum=0;cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)    {cin>>v[i];sum+=v[i];maxn=max(v[i],maxn);}
    sum-=maxn;
    if(sum<maxn)    cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

发表于 2022-01-14 01:13:12 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>v(n);
    int sum = 0;
    for(int i=0;i<n;++i){
        cin>>v[i];
        sum+=v[i];
    }
    sort(v.begin(),v.end());
    // 最大的组卷子比其他组之和还大 必定会拿回自己的卷子
    int flag = sum-v[n-1]>=v[n-1] ? 1:0;
    cout<<(flag?"Yes":"No")<<endl;
    return 0;
}
发表于 2020-06-18 21:29:52 回复(0)
二手独轮车头像 二手独轮车 
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a;cin>>a;
    int s=0;
    int *b=new int[a];
    for(int i=0;i<a;i++)
        cin>>b[i];
    sort(b,b+a);
    for(int j=0;j<a-1;j++)
        s+=b[j];
    if(s>=b[a-1])
        cout<<"Yes"<<endl;
    if(s<b[a-1])
        cout<<"No"<<endl;
    return 0;
}

发表于 2019-12-06 22:03:36 回复(0)
Python
白色纯度头像 白色纯度
这应该是最优解答了：
1. 只要组内的试卷最大数大于等于其余组试卷总和，那么最大组就有可能改到自己的卷子。
2. 至于卷子不够分配的情况，不存在的，倒序发收卷子即可！ 
if __name__=='__main__':
    n = int(raw_input().strip())
    num = list(map(int,raw_input().split()))
    key = max(num)
    if 2*key>sum(num):
        print 'No'
    else:
        print 'Yes'


发表于 2019-09-07 22:01:21 回复(0)
黄宗文头像 黄宗文
# 首先思路就是不能存在某一个组的人数超过剩下所有组人数的和
# 反过来说就是任何一个组的人数的2倍都不能超过总人数
def review(n, ln):
    total = sum(ln)
    for i in ln:
        if i*2 > total:
            return "No"
    else:
        return "Yes"
if __name__ == "__main__":
    n = int(input())
    ln = list(map(int, input().split()))
    print(review(n, ln))
发表于 2019-08-07 22:37:17 回复(0)
Python
雪糕爱菠萝🍍头像 雪糕爱菠萝🍍 

#coding'utf-8'
if __name__=='__main__':
    n=int(input())
    w=[int(i) for i in input().split()]
    count=0
    w.sort(reverse=True)
    for i in range(n):
        if sum(w[1:])<w[0]:
            print('No')
            break
        if w[0]<w[i]:
            print('No')
            break
        else:
            count=count+1
    if count==n:
        print('Yes')

发表于 2019-06-19 15:07:59 回复(0)
渡口的小太阳头像 渡口的小太阳
啥破题，看题目半个小时，写代码两分钟。。。。 
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arrs=new int[n];
        for(int i=0;i<n;i++){
            arrs[i]=sc.nextInt();
        }
        Arrays.sort(arrs);
        int temp=arrs[n-1];
        for(int i=n-2;i>=0;i--){
            temp-=arrs[i];
        }
        if(temp<=0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

发表于 2019-05-28 20:04:24 回复(0)
啥玩意😭头像 啥玩意😭 
import  java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int len = input.nextInt();
        int a[] = new int[len];
        for(int i = 0;i<len;i++)
            a[i] = input.nextInt();
        Arrays.sort(a);
         int sum = 0;
        for(int i = len-2;i>=0;i--){     
            sum = sum+a[i];
        }
        if(a[len-1]>sum)
            System.out.println("No");
        else
            System.out.println("Yes");
    }
}

发表于 2019-04-17 21:44:47 回复(0)
你的好友菜鸡上线头像 你的好友菜鸡上线 
//找最大的一组作为第一组，如果老师回到第一组的时候，第一组试卷没发完，就是No
#include<iostream>
using namespace std;
int main() {
    int n,s,t=0,max=0;
    cin>>n;
    while(n--){
        cin>>s;
        if(s>max)max=s;
        t+=s;
    }
    if(max>(t-max))cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

发表于 2019-03-14 15:41:08 回复(0)
提交观点

问题信息

模拟
难度：
15条回答 3819浏览

热门推荐

通过挑战的用户

查看代码

相关试题

改考卷

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号