YACS20222丙组——缩进对齐（差分法）

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

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

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

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

如果我们选择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;
}

最后

以上就是坦率纸鹤为你收集整理的YACS20222丙组——缩进对齐（差分法）的全部内容，希望文章能够帮你解决YACS20222丙组——缩进对齐（差分法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。