首页 > 试题广场 >

改考卷

[编程题]改考卷
  • 热度指数: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 的组。
当访问第 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)