首页 > 试题广场 >

改考卷

[编程题]改考卷
  • 热度指数: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 的组。
头像 白伟仝
发表于 2020-06-27 16:31:28
最大组的成员数量,小于等于总人数一半即可: import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); 展开全文
头像 17c89
发表于 2024-01-11 10:34:08
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(S 展开全文
头像 bandiaoz
发表于 2024-12-29 02:09:17
解题思路 这是一个贪心算法问题。具体要求: 个组的试卷需要批改,第 组有 个学生 每次从桌上取出一组试卷进行批改 批改完后,将学生自己的试卷放在桌面试卷最下方 需要判断是否存在一种访问顺序,使得每组学生都能拿到自己的试卷 解决方案: 找出人数最多的组 计算其他所有组的总人数 如果 , 展开全文