Leaving Auction

Leaving Auction

题目链接：http://codeforces.com/contest/749/problem/D

二分

本来以为是哪种神奇的数据结构，没想到sort+lower_bonud就解决了，妙。

这道题的精髓在于将每个人出价的最大值记录下来，最后竞拍到的一定为没有leave的人中出价最高的那个人（因为It's guaranteed that the sum of k over all question won't exceed 200 000. 所以这个操作的总复杂度不会超过200 000）。而这个人的最低出价，只需要比第二个人的最高出价高即可，此操作可以用二分。//最后不得不说scanf和cin在没有关同步之前，差别真的很大...

代码如下：

 #include <cstdio>

 #include <vector>

 #include <iostream>

 #include <algorithm>

 #include <set>

 #define pb(x) push_back(x)

 #define N 200005

 using namespace std;

 int n,q,k,t,biggest[N],person[N];

 vector<int>man[N];

 bool cmp(int a,int b){

     return biggest[a]<biggest[b];

 }

 int main(void){

     scanf("%d",&n);

     for(int i=;i<=n;++i){

         int a,b;

         scanf("%d%d",&a,&b);

         man[a].pb(b);

         biggest[a]=b;

         person[i]=i;

     }

     sort(person+,person++n,cmp);

     scanf("%d",&q);

     while(q--){

         set<int>leave;

         scanf("%d",&k);

         for(int i=;i<k;++i){

             scanf("%d",&t);

             leave.insert(t);

         }

         int temp[],num=;

         temp[]=temp[]=;

         for(int i=n;i>=;--i){

             if(leave.count(person[i]))continue;

             temp[num++]=person[i];

             if(num==)break;

         }

         if(man[temp[]].size()==){

             printf("0 0\n");

             continue;

         }

         if(num==){

             int it=*lower_bound(man[temp[]].begin(),man[temp[]].end(),biggest[temp[]]);

             printf("%d %d\n",temp[],it);

         }else if(num==){

             printf("%d %d\n",temp[],man[temp[]][]);

         }

     }

 }

巴特西

Leaving Auction

最新文章

热门文章