hzau 1209 Deadline（贪心）

K．Deadline 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

排序，大于N的不用考虑，否则超时

贪心

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e6 + 5;
 5 
 6 int a[MAXN];
 7 int b[MAXN];
 8 int tot;
 9 
10 int main()
11 {
12     int n;
13     int i;
14     int j;
15     int maxB;
16     int lMaxB;
17 
18     while (~scanf("%d", &n)) {
19         int n2 = n;
20         for (i = 0; i < n; ++i) {
21             scanf("%d", &a[i]);
22             if (a[i] >= n2) {
23                 --i;
24                 --n;
25             }
26         }
27         //cout << n << endl;
28         sort(a, a + n);
29 
30         tot = 0;
31         b[tot++] = 1;
32         for (i = 1; i < n; ++i) {
33             maxB = -1;
34             for (j = 0; j < tot; ++j) {
35                 if (b[j] < a[i] && b[j] > maxB) {
36                     maxB = b[j];
37                     lMaxB = j;
38                     break;
39                 }
40             }
41 
42             if (maxB == -1) {
43                 b[tot++] = 1;
44             } else {
45                 ++b[lMaxB];
46             }
47 
48         }
49 
50         printf("%d
", tot);
51     }
52 
53     return 0;
54 }

View Code

但是为什么用set写超时呢，不是应该比数组遍历查找要快吗？

超时代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e6 + 5;
 5 
 6 int a[MAXN];
 7 
 8 struct cmp {
 9     bool operator()(int a, int b)
10     {
11         return a > b;
12     }
13 };
14 multiset<int, cmp> st;
15 
16 int main()
17 {
18     int n;
19     int i;
20     multiset<int, cmp>::iterator it;
21     int tmp;
22 
23     while (~scanf("%d", &n)) {
24         st.clear();
25         int n2 = n;
26         for (i = 0; i < n; ++i) {
27             scanf("%d", &a[i]);
28             if (a[i] >= n2) {
29                 --i;
30                 --n;
31             }
32         }
33         //cout << n << endl;
34         sort(a, a + n);
35 
36         st.insert(1);
37         for (i = 1; i < n; ++i) {
38             it = st.upper_bound(a[i]);
39             if (it == st.end()) {
40                 st.insert(1);
41             } else {
42                 tmp = *it + 1;
43                 st.erase(it);
44                 st.insert(tmp);
45             }
46         }
47 
48         printf("%d
", st.size());
49         
50     }
51 
52     return 0;
53 }

View Code

其实这题可以用任务数 / 天数，向上取整得到最少需要的人数，取最大值

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e6 + 5;
 5 
 6 int maxA;
 7 int b[MAXN];//b[i]保存当天要完成的任务数
 8 int sum[MAXN];//sum[i]代表之前一共要完成任务数
 9 
10 int main()
11 {
12     int n;
13     int i;
14     int a;
15     int ans;
16 
17     while (~scanf("%d", &n)) {
18 
19         memset(b, 0, sizeof(b));
20         for (i = 0; i < n; ++i) {
21             scanf("%d", &a);
22             if (a > n) {
23                 continue;
24             }
25             ++b[a];
26             if (a > maxA) {
27                 maxA = a;
28             }
29         }
30         //cout << n << endl;
31 
32         sum[0] = 0;
33         ans = 1;//最小为1个工人...//初始化为0不对。因为有可能所有日期都大于n，那么结果应该为1，而不是0
34         for (i = 1; i <= maxA; ++i) {
35             sum[i] = sum[i - 1] + b[i];
36             ans = max(ans, (sum[i] + i - 1) / i);
37         }
38 
39         printf("%d
", ans);
40     }
41 
42     return 0;
43 }

View Code