美团点评——改试卷

缺乏、安全感 2022-06-09 10:30 233阅读 0赞

**题目描述：**

在上小学的时候，我们经常碰到这样的事情：考试完后老师懒得改试卷，于是让我们同桌互换试卷后为对方批改。但是后来老师发现这样做容易出现作弊，于是他想了一个新办法。老师将同学分成了n组，其中编号为i的组中有Si个人，然后老师按某种顺序依次访问这些组。

对于他访问的第一个组，他会将这组内的所有试卷都收走，放置在桌上，对于他后续访问的每一个组，首先他会从桌上的试卷最上方拿出该组对应人数数量的试卷，随机分配给改组每个人一张试卷让他们进行批改，而后再将这组学生自己考的试卷收走放在桌面试卷的下面。当他访问完所有的组后他会将桌面上剩余的所有试卷随机分配给他第一个访问的组的学生进行批改。

但他发现这种方法有时候也会出现问题：有可能在中途访问到某个组的时候桌面上的试卷不够分配给这个组学生每人一张；也有可能最后会有学生分配到批改自己的试卷，而这两种情况时候出现是与他访问每个组的顺序有关的。现在他想知道是否存在一种访问顺序能够使以上两种情况都不出现，顺利完成试卷的批改呢？

**输入：**

第一行一个整数n，表示学生组数。2<=n<=30.

第二行包含n个整数，S1,S2,S3,...,Sn，分别表示每组学生的人数，1<=Si<=10000

**输出：**

若存在一种访问顺序能够使试卷顺利批改完成，输出Yes，否则输出No。

**样例输入：**

Input Sample 1

10 20

Input Sample 2

2 3 3 1

**样例输出：**

Output Sample 1

Output Sample 2

Yes

**Hint：**

对于第2组样例，我们可以选择先访问人数为3的组，在访问人数为3的组，在访问人数为1的组，最后访问人数为2的组。

**思路：**遍历一遍数组，寻找最大的值，如果最大值不大于剩余的人数，就能保证不出现第二种情况，对于第一种情况，只要每次选剩余组中最大的那一组，就能保证该不会出现。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
           int n;
           cin >> n;
           vector<int> arr(n);
           int sum = 0;
           int Max = 0;
           for (int i = 0; i < n; i++) {
                  cin >> arr[i];
                  Max = max(Max, arr[i]);
                  sum += arr[i];
           }
           if (Max > sum - Max)          //只要最大组人数小于剩余人数个数，就能保证第二种情况不会出现
                  cout << "No" << endl;
           else
                  cout << "Yes" << endl;
           return 0;
    }