Codeforces Round #636div3 D. Constant Palindrome Sum (划分区间,差分)

题意:给你一个长度为偶数n的数组,每次可以将一个元素修改为不大于k的值,要求每个a[i]+a[n-i+1]都相等,求最少操作多少次

题解:假设每一对的和都为sum,小的记为mn,大的记为mx;

枚举[2,2*k]的所有数x:

我们对每一对相应的数考虑,有三种情况:改一个数,改两个数,不改

　　 1.改一个数:当x∈[mn+1,mx+k]; ==》b[mn+1]+,1,b[mx+k+1]-1;

　　　 2.该两个数:当x∈[2,mn] || [mx+k+1,2*k]; ==》b[2]+2,b[mn+1]-2; b[mx+k+1]+2,b[2*k](最后一个,没必要变)

　　　 3.不改:x==sum

　　所以我们将每对数记录一个差分数组b[i], 维护区间然后还原即可.

代码:

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6 #include <stack>

 7 #include <queue>

 8 #include <vector>

 9 #include <map>

10 #include <set>

11 #include <unordered_set>

12 #include <unordered_map>

13 #define ll long long

14 #define fi first

15 #define se second

16 #define pb push_back

17 #define me memset

18 const int N = 1e6 + 10;

19 const int mod = 1e9 + 7;

20 using namespace std;

21 typedef pair<int,int> PII;

22 typedef pair<long,long> PLL;

23

24 int t;

25 int n,k,a[N];

26 int sum;

27 int mx,mn;

28 int main() {

29     ios::sync_with_stdio(false);

30     cin>>t;

31     while(t--){

32         cin>>n>>k;

33         int b[2*k+10];

34         me(b,0,sizeof(b));

35         for(int i=1;i<=n;++i) cin>>a[i];

36

37         for(int i=1;i<=n/2;++i){

38             sum=a[i]+a[n-i+1];

39             mn=min(a[i],a[n-i+1]);

40             mx=max(a[i],a[n-i+1]);

41

42             b[2]+=2;

43             b[mn+1]--;

44             b[mx+k+1]++;

45             b[sum]--;

46             b[sum+1]++;

47         }

48         int res=b[2];

49         for(int i=3;i<=2*k;++i){

50             b[i]+=b[i-1];

51             res=min(res,b[i]);

52         }

53         printf("%d\n",res);

54     }

55

56     return 0;

57 }

巴特西

Codeforces Round #636div3 D. Constant Palindrome Sum (划分区间,差分)

最新文章

热门文章