AT_abc338_d 题解

yyrwlj · 2024-01-27 22:26:52 · 题解

题意简述

有一个环，要按给定的顺序经过环上的一些节点，任选环上的一条边删除，最少需要经过几条边走完。

思路

先考虑如果不用删边，最短的路径应该怎么求。

一个点到下一个点，要么顺时针走，要么逆时针走，统计两者的较小值即可。

我们不去想删除一条边后的路径该怎么求，而要去想删哪条边的代价最小。

我们假设不删边时，顺时针走总是比逆时针走更优。

那么我们如果改成走逆时针，那么就会多出这两者之差的代价。

我们删掉顺时针走的路径上的任意一条边，都会导致我们只能转而去走逆时针。

显而易见的，我们可以使用差分，将更优的路径上的所有边都加上两个选择的差。

最后被加的数最小的边就是最优解，答案就是不删边的答案加上那条边被加的数。

Code

#include <iostream>
#include <cmath>
using namespace std;
const int N = 200005;
typedef long long LL;
int x[N], d1[N], d2[N];
LL d[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i=1;i<=m;i++)
        scanf("%d", &x[i]);
    LL ans = 0;
    for (int i=1;i<m;i++)
    {
        d1[i] = x[i + 1] - x[i];
        if (d1[i] <= 0)
            d1[i] += n;
        d2[i] = x[i] - x[i + 1];
        if (d2[i] <= 0)
            d2[i] += n;
        ans += min(d1[i], d2[i]);
        const int tmp = abs(d1[i] - d2[i]);
        if (d1[i] < d2[i])
        {
            d[x[i]] += tmp;
            if (x[i] < x[i + 1])
                d[x[i + 1]] -= tmp;
            else
            {
                d[1] += tmp;
                d[x[i + 1]] -= tmp;
            }
        }
        else if (d1[i] > d2[i])
        {
            d[x[i + 1]] += tmp;
            if (x[i + 1] < x[i])
                d[x[i]] -= tmp;
            else
            {
                d[1] += tmp;
                d[x[i]] -= tmp;
            }
        }
    }
    for (int i=2;i<=n;i++)
        d[i] += d[i - 1];
    LL mn = 9e18;
    for (int i=1;i<=n;i++)
        mn = min(mn, d[i]);
    cout << ans + mn;
    return 0;
}