美团点评2018校招在线考试-编程题二

发表于 | 分类于 ，

题目:改考卷

描述

在上小学的时候，我们经常碰到这样的事：
    考完试后老师懒得改试卷，于是让我们同桌相互交换试卷后为对方批改。但是后来老师发现这样作容易出现作弊，于是他想了一个新办法。老师将同学分成了 n 个组，其中编号为𝑖的组中有si 个人。然后老师会按某种顺序依次访问这些组。
    对于他访问的第一个组，他会将这组内的所有试卷都收走，放置在桌上；对于他后续访问的每一个组，首先他会从桌上的试卷最上方拿出该组对应人数数量的试卷，随机分配给该组每个人一张试卷让他们进行批改，而后再将这组学生自己考的试卷收走放置在桌面试卷的最下方。当他访问完所有的组后他会将桌面上剩余的所有试卷随机分配给他第一个访问的组的学生进行批改。
    但他发现这种方法有时候也会出现问题：有可能在中途访问到某个组的时候桌面上的试卷不够分配给这组学生每人一张；也有可能最后会有学生分配到批改自己的试卷，而且这两种情况是否出现是与他访问每个组的顺序有关的。现在他想知道是否存在一种访问顺序能够使以上两种情况都不出现，顺利完成试卷批改呢？

输入

第一个整数 n，表示学生组数。2 ≤ n ≤ 30
第二行包含 n 个整数，s1 ,s2 ,…,sn ，分别表示每组学生的人数。1 ≤ si ≤ 10000

输出

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

Example

Input

2
10 20
4
2 3 3 1

Output

No
Yes

题解

思路

  • 把 s1…sn 按降序排列,不会出现第一种情况
  • 若人数最多的一组的人数不比其他所有组的人数之和,则不会出现第二种情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>

using namespace std;

int n,group[30];

int main()
{
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            cin>>group[i];
        }
        sort(group,group+n);
        for(int i=n-2;i>=0;--i)
        {
            group[i]+=group[i+1];
        }
        if(group[0]<(group[n-1]<<1))
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
}