HZAU 1209 Deadline （技巧）

HZAU 1209 Deadline （技巧）

Description

There are N bugs to be repaired and some engineers whose abilities are roughly equal. And an engineer can repair a bug per day. Each bug has a deadline A[i].Question: How many engineers can repair all bugs before those deadlines at least?1<=n<= 1e6. 1<=a[i] <=1e9

Input Description

There are multiply test cases.In each case, the first line is an integer N , indicates the number of bugs.The next line is n integers indicates the deadlines of those bugs.

Output Description

There are one number indicates the answer to the question in a line for each case.

Input

41 2 3 4

Output

1

题意

程序员一天可以修改一个 ​​bug​​​ ，现在给你一些 ​​bug​​ 以及其修复期限，问最少需要多少个程序员才可以完成任务。

思路

首先因为 n 的范围是 [1,106] ，也就是最多有 106 个 ​​bug​​ 。

假如每一个 ​​bug​​​ 找一个程序员来改，那么总共最多有 106 个程序员使用一天的时间完成所有任务，所以修复期限在 106 以上的 ​​bug​​ 我们不用考虑，因为它总能被修复。

对于前 i 天需要修复的 ​​bug​​ ，我们把它在 i 天内平均分配给的人数至少是 (sum−1)/i+1 ，也就是 ⌈sum/i⌉

AC 代码

#include #include #include #include using namespace std;int a[1000009];const int maxn = 1e6;int main(){ int n,b; while(~scanf("%d",&n)) { memset(a,0,sizeof(a)); for(int i=1; i<=n; i++) { scanf("%d",&b); if(b<=maxn)a[b]++; } int sum=0,ans=1; for(int i=1; i<=maxn; i++) { sum+=a[i]; int t=((sum-1)/i+1); ans=max(ans,t); } printf("%d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。