<span>codeforces725F Family Photos（贪心）</span>
原博客地址：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 <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #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<int,int> #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; }
网易公司福利 162人发布