Constant Palindrome Sum
需要知识：差分数组
题意：对于数列，使a[i]+a[n-i+1]=x,用[1,k]之间任意一个数替换a[i]或者是a[n-i+1],求出替换最小的次数。
这道题用的是差分数组，用差分数组维护x=[2,2k]的次数。这道题我是没有想出来，看了题解才知道，而且差分我也很少运用，算是盲区了
对于每对a[i]+a[n-i+1],设置sum=a[i]+a[n-i+1],minn=min(a[i],a[n-i+1]),maxx=max(a[i],a[n-i+1]).
当x=[2,minn]时，两个数必须都修改，因为a[i]最小为1嘛.
当x=[minn+1,sum-1],[sum+1,maxx+k]，修改一个数
当x[maxx+k+1,2k]修改两个数
最后的出来的是次数，而不是那个数字，所以用差分还是很好做的
import java.util.*; public class pd{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0){ int n = sc.nextInt(); int k = sc.nextInt(); int[] a = new int[n]; int[] cnt = new int[2*k+1]; int[] pref = new int[2*k+2]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } for(int i=0;i<n/2;i++){ cnt[a[i]+a[n-i-1]]++; } for(int i=0;i<n/2;i++){ //int l1=a[i]+1; //int r1 = a[n-i+1]+1; //int l2 = a[i]+k; //int r2 = a[n-i+1]+k; int l = Math.min(a[i],a[n-i-1])+1; int r = Math.max(a[i],a[n-i-1])+k; pref[l]++; pref[r+1]--; } for(int i=1;i<=2*k+1;i++){ pref[i]+=pref[i-1]; } int ans = Integer.MAX_VALUE; for(int sum=2;sum<=2*k;sum++){ ans = Math.min(ans,pref[sum]-cnt[sum]+(n/2-pref[sum])*2); } System.out.println(ans); } } }
