利用差分巧妙对每一个x进行尝试(CF1343D)

题目传送门

大致思路

由于数组中每个元素都不大于k,且即使替换后也满足$（1≤a_i≤k）$ ,故而最优 $x$ 在$[2,2k]$区间
由此可以想到好难想到,利用差分数组对每一个在区间内的x尝试,计算出对应的$x$需要修改多少次
对于任一$a_i$ , 计算$t=a_i+a_{n-i+1}$,对于$x==t$ 不做操作
对于任一 $x!=t$ :
如果$min(x,y)+1≤x≤max(x,y)+k$且 $x+y!=t$ ,对应的是该元素对只做一次修改便能满足的情况,对该区间的$x$的操作次数+1
对其他区间的$x$的操作次数+2
最后在还原数组的时候求最小值即可得出答案

Code

void solve() {
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1),d(2*k+2);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n/2;i++) {
        int x=a[i];
        int y=a[n-i+1];
        int t=x+y;
        int l=min(x,y)+1;
        int r=max(x,y)+k;
        d[2]+=2;
        d[l]--;
        d[r+1]++;
        d[t]--;
        d[t+1]++;
    }
    int ans=LLONG_MAX;
    for(int i=2;i<=2*k+1;i++) {
        d[i]+=d[i-1];
        ans=min(ans,d[i]);
    }
    cout<<ans<<endl;
}