Problem K: Deadline

Time Limit: 2 Sec Memory Limit: 1280 MB

Submit: 1106 Solved: 117

[Submit][Status][Web Board]

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

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

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

Sample Input

4

1 2 3 4

Sample Output

1

这道题的意思就是每件事都有个deadline，你一天只能做一件事情，我肯定贪心，先做要先完成了事啊，这个需要的程序员最少，可是1e6恐怕会超时的，所以需要对数据进行预处理，大于n的肯定可以做完了，题解上讲可以O(n)，用天数前缀和(s[i]-i+1)/i

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