가뭄 (Drought) (JUNGOL 5346)

https://jungol.co.kr/problem/5346

---

아이디어

h₁과 h₂를 같게 만들기 위한 유일한 방법은 h₂와 h₃에서 어떠한 수를 빼주는것입니다. 마찬가지로 h₃와 h_4를 같게 만들기 위한 유일한 방법은 h₄와 h₅에서 어떠한 수를 빼주는 것입니다. 만약 빼줄 수 없다면, 즉 더해주어야 같게 맞추어진다면 -1을 출력해주면 됩니다.

 

이를 반복하면 h₁과 h₂가 같아지고, h₃와 h₄가 같아지고,... 가 됩니다. 이때 N의 홀짝성에 따라서 풀이가 나누어지게 됩니다.

 

만약 N이 짝수라면, 먼저 h_N-1과 h_N이 같은지를 확인해주어야합니다. 만약 다르다면, -1을 출력해주면 됩니다. 만약 같다면, h₁과 h₂를 세트, h₃과 h₄를 세트, ... h_N-1과 h_N을 세트로 놓고 그 세트중 최솟값을 기준으로 모든 세트를 맞추어주면 됩니다. 그런데 만약 그 최솟값이 음수라면, -1을 출력해주고, 아니면 먹이를 준 값을 출력해주면 됩니다.

 

N이 홀수라면, 지금까지 했던 행동을 뒤에서부터 다시 해주면 됩니다. 그러면 모든 수가 같아지게 됩니다. 물론 이 경우에도 음수로 맞추어지는 경우는 빼주어야합니다.

---

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll arr[101010]={0};

void solve()
{
    ll N,i,res=0;

    cin>>N;
    for (i=1;i<=N;i++) cin>>arr[i];

    for (i=2;i<N;i+=2)
    {
        ll diff=arr[i]-arr[i-1];
        if (diff<0)
        {
            cout<<"-1\n";
            return;
        }
        arr[i]-=diff;
        arr[i+1]-=diff;
        res+=diff;
    }

    if (N%2==0)
    {
        if (arr[N]!=arr[N-1])
        {
            cout<<"-1\n";
            return;
        }
        ll mn=1e18;
        for (i=1;i<=N;i++) mn=min(mn,arr[i]);

        for (i=1;i<=N;i+=2)
        {
            res+=arr[i]-mn;
            arr[i]=arr[i+1]=mn;
        }
    }
    else
    {
        for (i=N-1;i>=2;i-=2)
        {
            ll diff=arr[i]-arr[i+1];
            if (diff<0)
            {
                cout<<"-1\n";
                return;
            }
            arr[i]-=diff,arr[i-1]-=diff;
            res+=diff;
        }
    }

    for (i=1;i<=N;i++)
    {
        if (arr[i]<0)
        {
            cout<<"-1\n";
            return;
        }
    }

    cout<<res*2<<"\n";
    return;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T;

    cin>>T;
    while (T--)
        solve();
}