Another Sorting Problem (CF R 1099 Div.2 - B)`

https://codeforces.com/contest/2231/problem/B

---

아이디어

a_i>a_i+1이라면 a_i에는 더하지 말고 a_i+1에는 k를 더해주어야합니다. 이를 앞에서부터 보면서 시행해주다가, k를 더해주어도 a_i보다 작다면 불가능한것입니다.

---

소스코드

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

ll arr[202020]={0};

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

    cin>>T;
    while (T--)
    {
        cin>>N;

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

        ll mx=0;
        for (i=1;i<=N-1;i++)
            mx=max(mx,arr[i]-arr[i+1]);

        bool able=true;
        for (i=1;i<=N-1;i++)
        {
            if (arr[i]>arr[i+1])
            {
                arr[i+1]+=mx;
                if (arr[i]>arr[i+1]) able=false;
            }
        }

        if (able) cout<<"YES\n";
        else cout<<"NO\n";
    }
}