当前位置: 首页 > 工具软件 > YACS > 使用案例 >

YACS20222丙组——缩进对齐(差分法)

陶和歌
2023-12-01

上海市计算机学会竞赛平台 | YACS

首先本题是一定有解的。我们可以每次只选择a中的一个元素,让它不停加1或者减1变成b数组中对应的值。

其次,本题中“需要保证a数组中的每一个元素都大于等于0”这个条件可以忽视。因为对于任意把a变成b的一系列操作,我们可以先执行其中加1的部分,然后再执行减1的部分,这样就能保证操作过程中每个元素都大于等于0.

然后,因为本题涉及的操作是连续若干个数字的加减,我们选取差分的视角来看这个操作,其实会简单很多。

 

ab
a132b1
a247b2
a358b3

ab
a000
c13a132d12
c21a247d25
c31a358d31
c4-5a400d4-8

如果我们选择a[1]到a[4]加1,体现在差分数组上则是c[1]加1,c[5]减1.

因为我们补充定义了a数组的头尾是0,其实差分数组c的和一定为0,类似地我们对b数组补充定义,另d数组为b数组的差分数组

则 “把a数组变成b数组” 等价于 “把c数组变成d数组”

而c数组每次操作的效果为任意选取两个数,另其中一个加1,另一个减1.

为了求出把c数组变成d数组要最少多少次,我们只需找出所有比 d[i]d[i] 大的 c[i]c[i],计算出 c[i]-d[i]c[i]−d[i]的和即可。(也可以找比d[i]d[i]小的c[i]c[i],结果一样)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N], d[N]; // c是a的差分数组,d是b的差分数组
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    a[0] = b[0] = a[n + 1] = b[n + 1] = 0;
    int ans = 0;                     //用来记录我们所需要的最小的操作的次数
    for (int i = 1; i <= n + 1; i++) 
    {
        c[i] = a[i] - a[i - 1];
        d[i] = b[i] - b[i - 1];
        if (c[i] >= d[i])
        {
            ans += c[i] - d[i];
        }
    }
    cout << ans;
    return 0;
}

 类似资料: