自动搬运

查看原文

来自洛谷，原作者为

	Nevergonna_CCF 当你看到这句话时，说明你的关注列表又多了一个人

搬运于2025-08-24 22:35:54，当前版本为作者最后更新于2022-02-04 11:50:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8092 [USACO22JAN] Drought B

该题是USACO1月铜组T3，蒟蒻在最后三分钟AC了这道题，不得不说，该题思维难度较大还是很简单的。

首先我们观察一下样例的第二个序列： 4 6 4 4 6 4

很明显，我们要尽可能的让这个序列所有值相差最少，就要让最大的降低，和他周围的尽量保持一致。

具体步骤

首先我们从下标为1的元素开始正序判断这个序列——如果当前 $h_{i}$ 大于 $h_{i+1}$ 或 $h_{i-1}$ ,判断 $h_{i+1}$ 和 $h_{i-1}$ 谁大。如果 $h_{i+1}$ 大，则将 $h_{i}$ 和 $h_{i-1}$ 自减到 $h_{i} = h_{i+1}$，反之亦然。

经过上面的步骤，我们肯定能得到一个单调递增的序列，我们在反序一次就行了，最后输出减了多少次。

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100001;

int n;
int a[MAXN];
unsigned long long ans = 0;

void func()
{
    memset(a, 0x3f3f3f3f, sizeof(a));
    ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (n == 2)
    {
        cout << (a[1] == a[2] ? 0 : -1) << endl;
        return;
    }
    for (int i = 2; i < n; i++)
    {
        if (a[i] > a[i+1])
        {
            int t = a[i] - a[i+1];
            a[i-1] -= t;
            a[i] -= t;
            ans += t * 2;
        }
        if (a[i] > a[i-1])
        {
            int t = a[i] - a[i-1];
            a[i+1] -= t;
            a[i] -= t;
            ans += t * 2;
        }
    }
    for (int i = n - 1; i >= 2; i--)
    {
        if (a[i]>a[i+1])
        {
            int t = a[i] - a[i+1];
            a[i-1] -= t;
            a[i] -= t;
            ans += t * 2;
        }
        if (a[i] > a[i-1])
        {
            int t = a[i] - a[i-1];
            a[i+1] -= t;
            a[i] -= t;
            ans += t * 2;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (a[i] != a[i + 1] || a[i] < 0)
        {
            cout << -1 << endl;
            return;
        }
    }
    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        func();
    }
    return 0;
}