HAZU校赛 Problem K: Deadline

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 <bits/stdc++.h>
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;
}