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

4
1 2 3 4

Output

1

题意

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

思路

首先因为 $n$ 的范围是 $[1,10^6]$ ，也就是最多有 $10^6$ 个 bug 。

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

对于前 $i$ 天需要修复的 bug ，我们把它在 $i$ 天内平均分配给的人数至少是 $(sum-1)/i+1$ ，也就是 $\lceil sum/i\rceil$ ，然后找最大的值即可。

AC 代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
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;
}