C - Constant Palindrome Sum 解题报告

题目链接：https://vjudge.net/contest/381753#problem/C
解题报告：
题目大意：
要满足ai都小于等于k，且所有ai+an-i+1都相同。问最少从a中更改几个数？
(1<= a <= k)
假设ai+an-i+1 = x, 这个x有很多可能。

设minn = min(ai, an-i+1)
maxn = max(ai, an-i+1)
分类讨论：
当x位于[2,minn],需要更改ai和an-i+1(2)
当x位于[minn+1,minn+maxn-1]，需要更改其中一个(1)
当x位于[minn+maxn]，不需要更改(0)
当x位于[minn+maxn+1, 2*k]，需要更改ai和an-i+1(2)

把s[i]记作x等于i时从a中更改多少个数。
我们想到对区间的修改可以用差分来处理。
最后求个前缀和取最小值即可得到答案。
于是代码便呼之欲出了。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5+7;
template<class T>inline void read(T &res){char c;T flag=1;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;}

int a[MAXN];
int s[2*MAXN];

int main()
{
    int t;
    read(t);
    while(t--) {
        memset(s, 0, sizeof(s));
        int n, k;
        read(n); read(k);
        for(int i = 1; i <= n; i++) {
            read(a[i]);
        }
        for(int i = 1; i <= n/2; i++) {        
            int j = n - i + 1;
            int sum = a[i]+a[j];
            int minn = min(a[i], a[j]);
            int maxn = max(a[i], a[j]);
            s[2]+=2;
            s[minn+1]-=2;     //在[2,minn]范围内都换2次 
            s[minn+1]++;        //在[minn+1, sum-1],[sum+1,maxn+k]范围内都换1次 
            s[sum]--;
            s[sum+1]++;
            s[maxn+k+1]--; 
            s[maxn+k+1]+=2;      //在[maxn+k,2*k]，两项都换 
        }
        int ans = cnt[2];
        for(int i = 3; i <= 2*k; i++) {
            s[i] += s[i-1];
            ans = min(ans, s[i]);
        }
        printf("%d\n",ans);
    }
 }