Codeforces1474D. Cleaning（前缀和/思维）_有一个数组,每次操作可以选择相邻的数,同时减一

Codeforces Round #696 (Div. 2) 全文见：https://blog.csdn.net/qq_43461168/article/details/112856420

D. Cleaning

题意：一个数组。每次可以选择两个相邻的数，同时减小1。而且允许交换两个数，最多操作一次。问是否能最后全变成0。

思路：前后缀和。第一个数，肯定是和第二个数一起减。并且减到0的。同理第二个数还要和第三个数一起减。那么从左往右这样可以一直减下去。就变成了一个，a₁,a₂-a₁,a₃-a₂+a₁…这样的数组。存起来作为前缀和pre[]，如果pre[n] == 0 则说明，减到最后大家都是0了。已经满足题意了，可以提前结束。同理，从右往左也这样进行一次。存起来作为后缀和suf[]。要保证数组都是非负数，不合法的可以进行标记。然后可以想到，如果 pre[i] == suf[i+1]，那么这两个数相等。再一减。不就全变成0了嘛。因为从左往右的都清零了。从右往左也清零了。就剩这两个独苗。如果他们相等显然就全清零了。这是不交换的状态。如果交换两个数呢。如图。如果要交换的元素是a[i] 和 a[i-1]，那么受到影响的就是pre[i] 和 suf[i+1]的值。具体来说，就是pre[i] = a[i+1]-pre[i-1] , suf[i+1] = a[i] - suf[i+2]。如果现在这两个值相等。也就是 pre[i] == suf[i+1]，则说明交换之后，满足清零的条件了！输出YES。如果所有位置都枚举了一遍。还是不行，那就是真的不行了。输出NO。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 3e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int sel = 0;
int pre[N];
int suf[N];
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1 ; i <= n ;i ++)
            cin>>a[i];
        for(int i=  1; i <= n ; i ++){
            if(pre[i-1] == -1 || a[i] < pre[i-1]){
                pre[i] = -1;
            }else{
                pre[i] = a[i]-pre[i-1];
            }
        }
        suf[n+1] = 0;
        for(int i = n ; i >= 1; i --){
            if(suf[i+1] == -1 || a[i] < suf[i+1]){
                suf[i] = -1;
            }else{
                suf[i] = a[i]-suf[i+1];
            }
        }
        int res = 0;
        if(pre[n] == 0) res = 1;
        for(int i = 1; i < n ; i ++){
            if(pre[i-1] == -1 || suf[i+2] == -1) continue;
            else{  // swap a[i] with a[i-1]
                if(a[i] >= suf[i+2] && a[i+1] >= pre[i-1] &&
                   a[i+1]-pre[i-1] == a[i]-suf[i+2]){
                    res = 1;break;
                }
            }
        }
        puts(res ? "YES" : "NO");
        cas++;
    }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52