首页 > 代码库 > uva11054 - Wine trading in Gergovia（等价转换，贪心法）
uva11054 - Wine trading in Gergovia（等价转换，贪心法）
这个题看上去麻烦，实际上只要想清楚就很简单。关键是要有一种等价转换的思维方式。其实题意就是个一排数，最后通过相邻的互相移动加减使得所有数都变成零，移动过程中每次都耗费相应值，让耗费的值最小。虽然从实际看来只能从负的移给正的，但实际结果谁给谁消耗的都一样。
有了这些等价思考，就可以用贪心法做了：第一个数要想变成0，那么必须和第二个数相互移，那么不管谁移给谁，消耗的就是第一个数的绝对值，最后第一个数变0，第二个数变a[1]+a[2]了。这样第2至n个数还是这样的思考方式。这种做法的每一步的消耗都是必不可少的，如果这这样的结果还小，那就不可能每个数都变成0了，所以这么贪心出来的结果是最优解。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long int#define maxn 100000+10int n,a;LL ans=0,t=0;int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d",&n)==1&&n) { ans=0; t=0; for(int i=0;i<n;i++) { scanf("%d",&a); t+=a; ans+=abs(t); } printf("%lld\n",ans); } //fclose(stdin); //fclose(stdout); return 0;}
uva11054 - Wine trading in Gergovia（等价转换，贪心法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。