hdu 4268 Alice and Bob(STL版)

http://acm.hdu.edu.cn/showproblem.php?pid=4268

　　这是今天网络赛的水题，下午短路了，没想到怎么做。队友hq是用treap做的，不过赛后我才想懂怎么做，回到宿舍快速打了一个，立马就一个1y了。。。。

　　这题跟以前做的数星星十分相似，转化过去其实就是在指定坐标与其左下方的点匹配。我用线段树做，如果自己打数据结构，可以用treap，也可以直接利用multi_set来当treap用。这题的时限挺长的，所以用了大量的STL都没超时。

3000ms+的代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <map>
  5 #include <set>
  6 #include <vector>
  7 #include <algorithm>
  8 #include <queue>
  9 
 10 #define lson l, m, rt << 1
 11 #define rson m + 1, r, rt << 1 | 1
 12 
 13 using namespace std;
 14 
 15 const int maxn = 100005;
 16 typedef pair<int, int> pii;
 17 
 18 vector<int> rec_w;
 19 set<int> Wide;
 20 map<int, int> Pos;
 21 int cnt[maxn << 3];
 22 priority_queue<pii, vector<pii>, greater<pii> > Alice, Bob;
 23 
 24 void add(int k, int l, int r, int rt){
 25     if (l == r){
 26         cnt[rt]++;
 27         return ;
 28     }
 29     int m = (l + r) >> 1;
 30 
 31     if (k <= m) add(k, lson);
 32     else add(k, rson);
 33 
 34     cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
 35 }
 36 
 37 bool find(int k, int l, int r, int rt){
 38     if (l == r){
 39         cnt[rt]--;
 40         return true;
 41     }
 42     int m = (l + r) >> 1;
 43 
 44     if (k > m && cnt[rt << 1 | 1]){
 45         if (find(k, rson)){
 46             cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
 47             return true;
 48         }
 49     }
 50     if (cnt[rt << 1] && find(k, lson)){
 51         cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
 52         return true;
 53     }
 54 
 55     return false;
 56 }
 57 
 58 int deal(int n){
 59     int l, w;
 60     int ret = 0;
 61 
 62     rec_w.clear();
 63     Wide.clear();
 64     Pos.clear();
 65     while (Alice.size()) Alice.pop();
 66     while (Bob.size()) Bob.pop();
 67 
 68     for (int i = 0; i < n; i++){
 69         scanf("%d%d", &l, &w);
 70         Alice.push(make_pair(l, w));
 71         Wide.insert(w);
 72     }
 73     for (int i = 0; i < n; i++){
 74         scanf("%d%d", &l, &w);
 75         Bob.push(make_pair(l, w));
 76         Wide.insert(w);
 77     }
 78 
 79     for (set<int>::iterator ii = Wide.begin(); ii != Wide.end(); ii++){
 80         Pos[*ii] = rec_w.size();
 81         rec_w.push_back(*ii);
 82     } // hash
 83 
 84     memset(cnt, 0, (rec_w.size() << 2) * sizeof(int));
 85     while (Alice.size()){
 86         while (Bob.size() && Bob.top().first <= Alice.top().first){
 87             add(Pos[Bob.top().second], 0, rec_w.size() - 1, 1);
 88             Bob.pop();
 89         }
 90 #ifndef ONLINE_JUDGE
 91         for (int i = 0; i < (rec_w.size() << 1); i++) printf("%d : %d\n", i, cnt[i]);
 92         printf("find pos %d\n", Pos[Alice.top().second]);
 93 #endif
 94         if (find(Pos[Alice.top().second], 0, rec_w.size() - 1, 1)) ret++;
 95         Alice.pop();
 96     }
 97 
 98     return ret;
 99 }
100 
101 int main(){
102     int T, n;
103 
104     scanf("%d", &T);
105     while (T-- && ~scanf("%d", &n)){
106         printf("%d\n", deal(n));
107     }
108 
109     return 0;
110 }

——written by Lyon