前情提要,结合原题解区的题解
题解
先简化问题,对于一对数 \(a,b\),其中 \(a\leq b\),要使其差为 \(X\) 的操作数是多少?
分类讨论
1.如果 \(b-a==X\),操作数为 \(0\)(不操作)
2.如果 \(X\lt b-a\),操作数为 \(1\)(增加a或者减小b)
3.如果 \(X \in [b-a+1,k-a]\),操作数为 \(1\)(增大b)
4.如果 \(X\in [b-a+1,b]\),操作数为 \(1\)(减小a)
5.否则操作数为 \(2\)(增加b,同时减小a)
实现
对于 \(X\in[0,b-a)\cup [b-a+1,\max(k-a,b)]\) 的区间操作数为 1
对于 \(X\in[b-a,b-a]\) 的区间,操作数为 \(0\)
对于 \(X\in(\max(k-a,b),k]\) 的区间,操作数为 \(2\)
相当于区间修改,单点查询(一次),因此可以用差分数组解决
code
class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n=nums.size();
vector<int> d(k+3,0);
for(int i=0;2*i<n;i++)
{
int a=min(nums[i],nums[n-i-1]);
int b=max(nums[i],nums[n-i-1]);
int m1=b-a;
int m2=max(k-a,b);
d[0]++;
d[m1]--;
d[m1+1]++;
d[m2+1]--;
d[m2+1]+=2;
d[k+1]-=2;
}
int ans=d[0];
for(int i=1;i<=k;i++)
{
d[i]+=d[i-1];
ans=min(ans,d[i]);
}
return ans;
}
};
标签:改动,操作数,int,3224,差值,数组,题解,区间,max
From: https://www.cnblogs.com/pure4knowledge/p/18350861