codeforces725F Family Photos（贪心）-白红宇

codeforces725F Family Photos（贪心）

阅读量：7219 次

发布时间：2019-06-29

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

原博客地址：http://blog.csdn.net/aufeas/article/details/53064649

题目大意：有n对照片，两个人A和B轮流取。每对照片有四个值a1,b1,a2,b2，表示第一张和第二张对A和B来说的喜悦值，只有第一张被取走时才能取第二张。轮到一个人时，她可以选择不取，如果连续两轮中A和B都选择不取那么游戏结束。她们都希望自己的喜悦值-对方的喜悦值的差值尽量大。假设两个人都采用最佳策略，求最后A的喜悦值和B的喜悦值的差值。

数据范围：1 ≤ n ≤ 100 000, 0 ≤ a1,b1,a2,b2 ≤ 10^9

题解：这是一道贪心好题（总之蒟蒻我想不到）。假设最后A的喜悦值为a，B的喜悦值为b，那么A希望a-b尽量大，B希望a-b尽量小（即b-a尽量大）。分多种情况讨论：

1.a1+b1 >= a2+b2，此时a1-b2 >= a2-b1。如果A取第一张，那么a-b较大；如果B取第一张，那么a-b较小。所以她们都希望自己先取。

2.a1+b1 < a2+b2且a1 > b2，此时一定是对方取第一张对自己来说更优，她们都不希望自己先取。但是对A来说，如果B一直不取，那么A取第一张，a1-b2 > 0也是对A有利的。因此对于这种情况，A会一直忽视这对照片，直到B第一次不取，这个时候A只能取第一张照片，然后B取第二张。因此对答案的贡献是a1-b2。

3.a1+b1 < a2+b2且b1 > a2。同上一种情况类似，对答案的贡献是a2-b1。

4.a1+b1 < a1+b2且a1 <= b2且b1 <= a2。此时对A和B来说无论怎么取都会使情况更差，因此这对照片不会被取，只要把他们删掉就可以了。

通过以上讨论，我们只要考虑a1+b1>=a2+b2的情况就可以了。

考虑一张照片(a,b)，如果被A取走，对答案的贡献是a，如果被B取走，对答案的贡献是-b。那么我们把一张照片(a,b)换成((a+b)/2,(a+b)/2)，并把答案加上(a-b)/2。这样如果A取了这张照片，那么实际贡献(a-b)/2+(a+b)/2=a；B取走实际贡献(a-b)/2-(a+b)/2=-b。这样一来每张照片对A和B来说是一样的，我们只要排个序然后贪心即可。并且由于a1+b1>=a2+b2，所以第一张一定在第二张之前被取走。

另外，由于这样的照片的个数是偶数个，我们可以直接从小到大排，偶数给A，奇数给B。并且因为我们排序的根据是(a+b)/2，因此也可以直接将a+b排序，处理的时候可以把答案加上a，然后排序后，如果当前照片是给B的，就从答案中减去这个值，即a-(a+b)=-b。

时间复杂度O（nlogn）

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define pii pair
                  
                   #define mkp make_pair#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9;const int N=2e5+10;int n,m,a1,b1,a2,b2,a[N];LL ans;int main(){ scanf("%d",&n); while(n--) { scanf("%d%d%d%d",&a1,&b1,&a2,&b2); if(a1+b1>=a2+b2) { a[++m]=a1+b1; a[++m]=a2+b2; ans+=a1+a2; } else if(a1>b2) ans+=a1-b2; else if(b1>a2) ans+=a2-b1; } sort(a+1,a+m+1); for(int i=1;i<=m;i+=2) ans-=a[i]; printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/d-e-v-i-l/p/6107394.html

你可能感兴趣的文章