hdu 1050 Moving Tables (Greedy)

　　过两天要给12的讲贪心，于是就做一下水贪心练习练习。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <set>
 6 #include <vector>
 7 
 8 using namespace std;
 9 
10 typedef pair<int, int> PII;
11 typedef vector<PII> VPII;
12 
13 multiset<int> cor;
14 multiset<int>::iterator msi;
15 VPII rec;
16 VPII::iterator vi;
17 
18 int main() {
19     int n, T, l, r;
20     cin >> T;
21     while (T-- && cin >> n) {
22         cor.clear();
23         rec.clear();
24         for (int i = 0; i < n; i++) {
25             cin >> l >> r;
26             if (l > r) swap(l, r);
27             rec.push_back(PII(l + 1 >> 1, r + 1 >> 1));
28         }
29         sort(rec.begin(), rec.end());
30         vi = rec.begin();
31         cor.insert((*vi).second);
32         for (vi++ ; vi != rec.end(); vi++) {
33             msi = cor.lower_bound((*vi).first);
34             if (msi == cor.begin()) cor.insert((*vi).second);
35             else {
36                 msi--;
37                 cor.erase(msi);
38                 cor.insert((*vi).second);
39             }
40         }
41         cout << cor.size() * 10 << endl;
42     }
43     return 0;
44 }

View Code

——written by Lyon