首页 > 代码库 > hzau 1209 Deadline（贪心）
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\n", tot);51 }52 53 return 0;54 }
但是为什么用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\n", st.size());49 50 }51 52 return 0;53 }
hzau 1209 Deadline（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。