Canada Cup 2016 F. Family Photos(贪心,想法,好题)-白红宇的个人博客

Canada Cup 2016 F. Family Photos(贪心,想法,好题)

发布日期：2021-11-12 00:25:47 浏览次数：2 分类：技术文章

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

Alice and Bonnie are sisters, but they don't like each other very much. So when some old family photos were found in the attic, they started to argue about who should receive which photos. In the end, they decided that they would take turns picking photos. Alice goes first.

There are n stacks of photos. Each stack contains exactly two photos. In each turn, a player may take only a photo from the top of one of the stacks.

Each photo is described by two non-negative integers a and b, indicating that it is worth a units of happiness to Alice and b units of happiness to Bonnie. Values of a and b might differ for different photos.

It's allowed to pass instead of taking a photo. The game ends when all photos are taken or both players pass consecutively.

The players don't act to maximize their own happiness. Instead, each player acts to maximize the amount by which her happiness exceeds her sister's. Assuming both players play optimal, find the difference between Alice's and Bonnie's happiness. That is, if there's a perfectly-played game such that Alice has x happiness and Bonnie has y happiness at the end, you should print x - y.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the number of two-photo stacks. Then follow n lines, each describing one of the stacks. A stack is described by four space-separated non-negative integers a1, b1, a2 and b2, each not exceeding 109. a1 and b1 describe the top photo in the stack, while a2 and b2 describe the bottom photo in the stack.

Output

Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

     Examples 
       input 
212 3 4 71 15 9 1
       output 
1
       input 
25 4 8 84 12 14 0
       output 
4
       input 
10 10 0 10
       output 
-10

题意：

给出n对照片，Alice和Bonnie轮流取照片，每张照片有两个值a 和 b ，

a表示Alice取走这张照片获得的喜悦值，b表示Bonnie取走这张照片获得的喜悦值，

（每对照片只有当第一张照片被取走后才能取第二张），当轮到一个人时，他可以选择不取，当连续两轮两个人都不取时，游戏结束，

Alice 和 Bonnie都希望自己的喜悦值和对方的喜悦值差值最大，假设两人都采取最佳策略，求Alice 和 Bonnie最后的喜悦值的差值

数据：

1 <= n <= 100000

接下来n行每行四个非负整数 a1,b1,a2,b2

a1,b1代表第一张照片，a2,b2代表第二张照片

a1,b1,a2,b2 不超过1e9

题解：

贪心。
对于单张照片来看，因为目标是净胜分，所以价值可认为是a+b，但是由于有先后的约束，需要分类讨论。
对每对照片分类，共3类:
1 a1<=b2&&b1<=a2, 对于该对照片，双方第一次选择均为负收益，故直接忽略。
2 非1, 且a1+b1<=a2+b2, 即对于该对照片，双方的后手收益都好于先手收益，但是由于非1，必有a1>b2或b1>a2，即必有一方有正收益，所以这一方为了保证自己的正收益而不是零收益(忽略该物品)不得不选择先手。
3 其余情况。因为1和2排除了废物品和后手有利物品，其余物品可以正常选择，而显然因为目标是最大化净胜分，所以物品的价值可以定为a1+b1(第二轮则是a2+b2),正常的优先队列贪心即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define rep(i,a,n) for (int i=a;i
           
            =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
            
              VI;typedef long long ll;typedef pair
             
               PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=1e5+100;struct node{ ll a1,b1,a2,b2; int tag; node(ll a=0,ll b=0,ll c=0,ll d=0):a1(a),b1(b),a2(c),b2(d) {} bool operator <(const node &b)const{ return a1+b1
              
                q;int main(){ int n; scanf("%d",&n); ll ans=0; rep(i,1,n+1) { ll a1,b1,a2,b2; scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2); if(a1
               
                
                 =b2) ans+=a1-b2; else ans+=a2-b1; } else { node t=node(a1,b1,a2,b2); t.tag=1; q.push(t); } } int cnt=0; while(!q.empty()) { node t=q.top(); q.pop(); cnt++; if(cnt&1) ans+=t.a1; else ans-=t.b1; if(t.tag==1) { node t1=node(t.a2,t.b2,0,0); t1.tag=0; q.push(t1); } } printf("%lld\n",ans); return 0;}

转载地址：https://blog.csdn.net/fouzhe/article/details/55806016 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：gym 100820G Racing Gems(二维LIS,好题)

下一篇：hdu 5919 Sequence II(主席树)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章