Constant Palindrome Sum
题意：
给你一个长度为n的数组a，保证n是偶数，且a[i] <= k
你可以选择一个下标i ，在1~k范围内任意改变a[i]
求最少的操作次数使得所有的a[i] + a[n-i+1]都为x
思路：
对于每一个a[i] 和 a[n-i+1] ,我们有三种选择
1.不进行操作
2.对其中的一个数进行操作
3.对两个数都进行操作
我们记x = a[i]+a[n-i+1] , maxx=max(a[i],a[n-i+1]) , minn=min(a[i],a[n-i+1])
同样这三种选择也会对答案产生不同的贡献
1可以得到的x的范围是：minn+maxx
2可以得到的x的范围是：minn+1~maxx+k
3可以得到的x的范围是：2~2k
其实x并没有什么鲜明的性质，也就是说我们无法单单通过题干确定x的值，我们只能确定x的范围然后在这个范围里选择操作次数最少的x
举个栗子，第二种操作意味着什么呢？
意味着我可以用对[minn+1,maxx+k] 这段区间+1 ，表明对于此对a[i]和a[n-i+1]来说，我们可以通过操作次数1来对答案产生贡献。也就是说，对于一组数据，如果x在区间[minn+1,maxx+k] 内，这对数据的贡献就是1。
其他的也类似。
是不是很像差分呢233
因为数组后每一个更改后的数都不超过k，所以最后x的区间是在2~2k内，只需要遍历区间取min即可。
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e6+7; ll a[maxn],s[maxn]; int main(){ int t;cin>>t; while(t--){ ll n,k;cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; memset(s,0,sizeof s); for(int i=1;i<=n/2;i++){ ll sum=a[i]+a[n-i+1],maxx=max(a[i],a[n-i+1]),minn=min(a[i]a[n-i+1]); s[1]+=2;///边界处理 s[minn+1]--;s[maxx+k+1]++; s[sum]--;s[sum+1]++;///扣除重复的 } int res=0x3f3f3f3f; for(int i=1;i<=2*k;i++){ s[i]+=s[i-1]; res=min(res,s[i]); } cout<<res<<endl; } return 0; }
问题 A: 鸭子游戏
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
KeineDuck热爱游戏。最近她沉迷于一款名叫“DuckGame”的纸牌。
DuckGame是一款颇有难度的纸牌游戏。在每一轮开始前，会有一些纸牌摆放在玩家的面前，从左到右的第孩堆有ai张纸牌。每张纸牌都是一样的。
游戏开始后，玩家可以选择一个区间[l,r]（包括两个端点），并且把这个区中的每一堆纸牌增加或拿走一张纸牌。若每堆纸牌的个数都相同了，玩家即可获胜。我们称这个步骤为一次操作。
KeineDuck想要知道，她至少要进行多少次操作，才能够获胜。
输入
第一行输入一个正整数n，表示有多少堆纸牌。
接下来一行共n个数，第i个数表示第i堆有多少纸牌。
输出
一个整数，表示至少要多少次操作。
样例输入 Copy
5
2 1 2 3 3
样例输出 Copy
2
提示
样例解释
KeineDuck第一次选择了区间[2,2]，将其中的每堆增加了一张纸牌。
KeineDuck第二次选择了区间[4,5]，将其中的每堆拿走了一张纸牌。
总共用了2次操作。
对于10%的数据，n=2。
对于另外20%的数据，n=6。
对于另外10%的数据，n=10000，且纸牌的数量从左到右单调递增。
对于另外10%的数据，n=100000，且每堆纸牌的个数不超过2。
对于另外20%的数据，n=100000，且每堆纸牌的个数不超过20。
对于最后30%的数据，n=2000000，且每堆纸牌的个数不超过1000。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll ksm(ll a,ll b,ll p){ ll res=1; while(b){ //&运算当相应位上的数都是1时，该位取1，否则该为0。 if(b&1) res=1ll*res*a%p;//转换为ll型 a=1ll*a*a%p; b>>=1;//十进制下每除10整数位就退一位 } return res; } const int maxn=2000000+100; ll a[maxn]; map<int,int>mp; void AC(){ ll n;scanf("%lld",&n); ll sum1=0,sum2=0; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=n;i>1;i--) if(a[i]-a[i-1]>0) sum1+=a[i]-a[i-1]; else sum2+=a[i-1]-a[i]; printf("%lld\n",max(sum1,sum2)); } int main(){ AC(); return 0; }
