题解：AT_abc467_c [ABC467C] Adjacent Sums (easy)

Cookie_King · 2026-07-19 08:52:58 · 题解

Problem

给出两个由 0 至 M-1 之间的整数组成的整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,_2,\dots,B_{N-1})。 A 和 B 的长度分别为 N 和 N-1 。

多次对 A 执行以下操作。

选择 A 数组中的一个数，将 A_i 变成 A_i + 1。

求满足以下条件所需的最少操作次数。

对于 i=1,2,\dots,N-1 ， (A_i+A_{i+1}) \mod m = B_i 。
Solution

观察数据范围，发现 m = 2，也就是说 A 数组和 B 数组仅由 0 和 1 组成。这个限制条件把复杂的可能都排除了，那么很容易得出思路：讨论 A_1 的值是 1 还是 0，然后根据 B 数组生成整个序列，计算两种情况中操作次数最小的那个并输出。

题外话：赛时做这个题一开始还以为全都加在 A_{i+1} 上最优，吃了一发罚时，糖丸了。

Code

AC 记录

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n,m,a[N],b[N],f[N][2],ans1=0,ans2=0;
//f[i][0 ]是 A[1]=0 的时候 A[i] 的数，f[i][1] 是 A[1]=1 的时候 A[i] 的数
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<n;++i)
        scanf("%d",&b[i]);
    f[1][0]=0,f[1][1]=1;
    for(int i=2;i<=n;++i){
        f[i][0]=b[i-1]-f[i-1][0];
        if(f[i][0]<0)//这时 b[i-1]=0，A[i-1]=1，实际操作需要在 A[i] 上加一
            f[i][0]=1;//和原数组不一样就行，只是为了统计
        f[i][1]=b[i-1]-f[i-1][1];
        if(f[i][1]<0)//同理
            f[i][1]=1;
    }
    for(int i=1;i<=n;++i){
        if(a[i]!=f[i][0])
            ans1++;
        if(a[i]!=f[i][1])
            ans2++;
    }
    printf("%d\n",min(ans1,ans2));
    return 0;
}
/*
0 1 0
1 0 1
*/

题解：AT_abc467_c [ABC467C] Adjacent Sums (easy)

Problem

Solution

Code