1887: Deadline

Time Limit: 2 Sec     Memory Limit: 1280 MB Total Submissions: 53     Accepted: 7 [ Submit]   [ Statistic]   [ Go Back]

题目描述

     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 

输入描述

       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. 

输出描述

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

输入样例

4 1 2 3 4

输出样例

1

分析：

当数大于1e6时可不处理，根据抽屉原理即可得出

以下代码可AC，sort排序了也会超时，也是醉了

附上“超时代码”，避免了上面的情况，依然超时，至今不懂为什么会超时。。。。。。。。。。。。。。真的无语

AC代码如下：

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e6+10; int a[maxn]; int main() { int n,num; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); int sum=0; int maxi=1; for(int i=1;i<=n;i++) { scanf("%d",&num); if(num<=n) a[num]++; } for(int i=1;i<=n;i++) { sum+=a[i]; int cur=sum/i; if(sum%i!=0) cur++; maxi=max(maxi,cur); } printf("%d\n",maxi); } return 0; }

错误（系统判超时）代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e6+10; int a[maxn],b[maxn]; int main() { int n; while(cin>>n) { memset(b,0,sizeof(b)); int maxi=0; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]<maxn) b[a[i]]++; } for(int i=1;i<=maxn;i++) { b[i]+=b[i-1]; int cur=b[i]/i; if(b[i]%i!=0) cur++; maxi=max(maxi,cur); } cout<<maxi<<endl; } return 0; }