2015 多校联赛 ——HDU5360（贪心+优先队列）-白红宇

2015 多校联赛 ——HDU5360（贪心+优先队列）

阅读量：6360 次

发布时间：2019-06-23

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

Sample Input

      4 8 4 1 3 2 2 1 0 3 5 3 6 4 2 1 7 6 8 3 3 2 0 5 0 3 6 4 5 2 7 7 6 7 6 8 2 2 3 3 3 0 0 2 7 4 3 6 3 2 2 5 8 5 6 5 3 3 1 2 4 6 7 7 6 5 4 3 5 

Sample Output

      7 1 7 6 5 2 4 3 8 8 4 6 3 1 2 5 8 7 7 3 6 7 1 5 2 8 4 0 1 2 3 4 5 6 7 8 

找出能约出最多人的顺序。假设前面已经有x人同意了，对于第i个人而言， l[i] <= x <= r[i] ,则第i个人同意。求以怎样的顺序去找人最合适。

感觉思路大致方向是对的，只是方法上有些问题，不够简便（- -）

在同l都满足的情况下，选择的r要尽可能的小，才能保证后面选的更多

scanf("%d",&tmp);

q[p[i]].push_back(node(tmp,i));

p[i]是它的左边，tmp是右边，用这样保存的话在查找的时候便不用查找全部。（详细看代码）

每次查找后都保证了（l[i] <= i 的全部被包括了，感觉别人好机智。。）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;struct node{ int b, num; node() {} node( int _b, int _num ) { b = _b, num = _num; } bool operator < ( const node & l ) const { return b > l.b; }};int p[100010];int n;int rec[100010];int vis[100010];int aim;vector
           
            q[100010];priority_queue
            
             que;int main(){ int T; scanf("%d",&T); while(T--) { aim=0; memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i = 0;i <= n;i++) q[i].clear(); for(int i=1; i<=n; i++) { scanf("%d",&p[i]); } for(int i=1; i<=n; i++) { int tmp; scanf("%d",&tmp); q[p[i]].push_back(node(tmp,i)); //用左边界来记录 } while(1) { int flag = 0; for(int i=0; i < q[aim].size(); i++) //这里就不需要全部找一遍 { que.push(q[aim][i]); } while(!que.empty()) { if(que.top().b>= aim && vis[que.top().num]!=1) { vis[que.top().num]=1; rec[aim] = que.top().num; aim++; que.pop(); flag = 1; break; } que.pop(); } if(!flag) break; } printf("%d\n",aim); if(aim) { printf("%d",rec[0]); for(int i=1; i