本文主要是介绍[POJ 3045] Cow Acrobats （贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ - 3045
有若干头牛叠罗汉，每头牛有一个冒险值，为在其上面所有牛的重量，减去其力量值
问如何使得最大的冒险值最小
挑战上面的题，本来想着用二分答案的方法做
虽然觉得自己的思路没什么问题，但是 WA了
百度了一发题解，发现这题正解是贪心
首先直观感觉力量大的，体重轻的应该在下面，但这有两个因素，不好确定
可利用调整法试图找出答案
假设我已经找到了答案排列 （ 猜想答案序列）
证明任何一个调整都会使答案变劣，从而研究他的性质
不难发现，对于答案相邻的两只牛 a和 b （ a在 b下），改变它们的位置
只会改变它们的冒险值，而对其他的牛没有影响
Ra=sum+Wb−Sa
Rb=sum−Sb
改变位置
R′a=sum−Sa
R′b=sum+Wa−Sb
因为改变前答案更优，所以有
max(Ra,Rb)≤max(R′a,R′b)
发现 R′a≤Ra
若 R′a 是最大值，那么无论 Ra ， Rb 谁最大，均使得调整前的答案不是最优的，故矛盾
所以 R′b 是不等号右端的最大值
即有 R′b≤max(Ra,Rb) ，所以
sum+Wa−Sb≤sum+Wb−Sa
sum+Wa−Sb≤sum−Sb
由第一个式子可得，对于答案序列的任意两头相邻的牛 （a 在 b下）
Wa+Sa≤Wb+Sb
这个不等号具有传递性，所以答案序列中，任意两头牛 （a 在 b下）
Wa+Sa≤Wb+Sb
因此我们发现了答案序列一个很好的规律，于是对 W + S排序即可得到答案序列
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const int maxn=5e4+10;
const LL INF=0x3f3f3f3f;
int N;
LL tot;
Pii inpt[maxn];bool icmp(Pii u, Pii v)
{return u.first+u.second<v.first+v.second;
}bool judg(LL);int main()
{while(~scanf("%d", &N)){LL sum=0,tmax=-INF;for(int i=1; i<=N; i++) scanf("%lld%lld", &inpt[i].first, &inpt[i].second);sort(inpt+1,inpt+1+N,icmp);for(int i=1; i<=N; i++){tmax=max(tmax,sum-inpt[i].second);sum+=inpt[i].first;}printf("%lld\n", tmax);}return 0;
}这篇关于[POJ 3045] Cow Acrobats （贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
