[原创]华中农业大学第五届程序设计大赛 K Deadline []【思维】

2017-05-26 22:49:23 Tabris_ 阅读数：265

博客爬取于2020-06-14 22:40:27
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72775216

题目连接:http://acm.hzau.edu.cn/problem.php?id=1209

——————————————————————————
1209: Deadline
Time Limit: 2 Sec Memory Limit: 1280 MB
Submit: 1195 Solved: 139
[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

————————————————————————————
题目大意：
就是有n个bug，每个bug有一个ddl，问你最少需要多少人才能在保证在每个bug的ddl之前修好所有bug。

解题思路：

其实很好想，枚举ddl，计算这个ddl内有多少个bug需要解决，除一下向上取整就是当前所需要的最少人数，维护最大值就行了，

附本题代码
————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2e6+7;
//const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x;
}
/*******************************************/

int a[N];
int n;

int main(){//printf("%d\n",INF);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)    a[i]=read();
        sort(a+1,a+n+1);
        int mx = 1;
        for(int i=1;i<=n;i++)
            mx = (mx>((i+a[i]-1)/a[i]))?mx:((i+a[i]-1)/a[i]);
        printf("%d\n",mx);
    }
    return 0;
}