题意：看完电影后，乐乐回家玩起了积木。他已经搭好了。乐乐的积木都这了，也就是说不能添加新的积木，，只能移动现有的积木。他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".请你帮他算算，需要移动的最少积木数。题解：在原区间两侧各加一个长为w的全0序列，维护从0到i的一个区间全加数jia[i] 和 全减数cha[i],(完成这段区间只添加/减少所需),则区间0到i的答案为max(jia[i],cha[i]).时间卡的比较紧，使用快速读写。代码：#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N = 50000*3+100;typedef long long ll;const ll inf = 1e16;ll sum,cha[N],jia[N],ans;int n;ll m,w;int a[N],b;void in(int &x){char ch; int minus = 0;while (ch=getchar(), (ch<'0'||ch>'9') && ch!='-');if (ch == '-') minus = 1, x = 0;else x = ch-'0';while (ch=getchar(), ch>='0'&&ch<='9') x = x*10+ch-'0';if (minus) x = -x;}void in(ll &x){char ch; int minus = 0;while (ch=getchar(), (ch<'0'||ch>'9') && ch!='-');if (ch == '-') minus = 1, x = 0;else x = ch-'0';while (ch=getchar(), ch>='0'&&ch<='9') x = x*10+ch-'0';if (minus) x = -x;}void out(int x){char hc[30];int len, minus=0;if (x<0) minus = 1, x = -x;len = 0; hc[len++] = x%10+'0';while (x/=10) hc[len++] = x%10+'0';if (minus) putchar('-');for (int i=len-1; i>=0; i–) putchar(hc[i]);}void out(ll x){char hc[30];int len, minus=0;if (x<0) minus = 1, x = -x;len = 0; hc[len++] = x%10+'0';while (x/=10) hc[len++] = x%10+'0';if (minus) putchar('-');for (int i=len-1; i>=0; i–) putchar(hc[i]);}int main(){while(scanf("%d%lld%lld",&n,&m,&w)!=EOF){sum = 0;cha[0]=0;jia[0]=0;ans = inf;for(int i=1;i<=n;i++) in(a[i+m]);for(int i=1;i<=m;i++) a[i+n+m]=a[i]=0;for(int i=1;i<=n+m*2;i++){sum+=a[i];ll b=w-a[i];if(b>0)cha[i] = cha[i-1]+b , jia[i]=jia[i-1];elsejia[i] = jia[i-1]-b , cha[i] = cha[i-1];}if(sum < m*w ){puts("-1");continue;}for(int i=1;i<=n+m+1;i++){ll tmp = max(cha[i+m-1]-cha[i-1],jia[i+m-1]-jia[i-1]);ans = min(tmp,ans);}out(ans);putchar('\n');}return 0;}
上帝从不埋怨人们的愚昧，人们却埋怨上帝的不公
