P8092

Nevergonna_CCF · 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;
}