这个题看上去麻烦,实际上只要想清楚就很简单。关键是要有一种等价转换的思维方式。其实题意就是个一排数,最后通过相邻的互相移动加减使得所有数都变成零,移动过程中每次都耗费相应值,让耗费的值最小。虽然从实际看来只能从负的移给正的,但实际结果谁给谁消耗的都一样。
有了这些等价思考,就可以用贪心法做了:第一个数要想变成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+10 int 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; }