poj3614 Sunscreen（贪心+STL）-白红宇

poj3614 Sunscreen（贪心+STL）

阅读量：5090 次

发布时间：2019-06-13

本文共 1438 字，大约阅读时间需要 4 分钟。

如果这不是优先队列专题里的，我可能不一定能想到这么做。

结构体命名得有点不好，解题中看着Edge这个不恰当的命名，思路老是断掉。

贪心策略：先对牛按from升序，对瓶子按w升序，优先队列是按to的小顶堆；

　　　　然后枚举瓶子，只要当前牛的from<=当前瓶子的w就入队，直到不满足为止；

　　　　然后在队伍里取出一个，判断它的是否to>=w以及cover数是否还够用。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|110 #define INF 0x3f3f3f3f11 typedef unsigned long long ll;12 using namespace std;13 int n, m;14 struct Node{15 int from, to;16 int w;17 friend bool operator<(const Node a, const Node b){18 return a.to>b.to;//小顶堆按to排 19 }20 }node[3010];21 struct Edge{22 int w, cover;23 }edge[3010];24 bool cmp(const Edge a, const Edge b)25 {26 return a.w
            
              q; 35 cin >> n >> m;36 for(int i = 0; i < n; i++){37 cin >> node[i].from >> node[i].to;38 }39 for(int i = 0; i < m; i++){40 cin >> edge[i].w >> edge[i].cover;41 }42 sort(edge, edge+m, cmp);43 sort(node, node+n, cmp2);//一开始没加这个wa了好久 44 int k = 0, ans=0;45 for(int i = 0; i < m; i++){ //瓶子 46 while(k < n&&node[k].from<=edge[i].w){ //左边界在它的前面就入队 47 q.push(node[k]);48 k++;49 }50 while(!q.empty()){51 Node t = q.top(), p;52 q.pop();53 if(t.to>=edge[i].w&&edge[i].cover>0){ //两种都满足可以ans++ 54 edge[i].cover--;55 ans++;56 }57 if(edge[i].cover == 0) break;58 59 }60 }61 cout << ans << endl;62 return 0;63 }