어제 대회에서 나온 문제
https://codeforces.com/contest/1700/problem/C
대회 때는 그리디가 될거 같았는데, 자꾸 최근에 글을 올렸듯이 차이를 보는 것이 생각이 나서, 그렇게 생각을 하다보니까 조금 오래걸렸다.
이 문제도 차이를 보는 방식으로 하면 쉽게 풀린다. 왜 그렇나면, 연속된 구간에 1을 더하거나 전체 구간에 1을 빼는 방식은 다루기 까다롭다. 그런데, 현재 i번째 값과 i-1번째 값의 차를 새로운 dif[i]로 정의하면 쉽게 풀수가 있는데, 1~i까지 1을 더하는 방식은 dif[1]에 1을 더하고 dif[i+1]에 1을 빼는것과 동일하고, i부터 n까지 1을 더하는 것은 dif[i]에 1을 더하는 것과 동일하기 때문이다. 그리고 전체 구간에 1을 빼는 것은 dif[1]에 1을 빼는 것이다. 그렇다면 이제 문제를 어떻게 풀지는 간단해졌다. 모든 ai가 0이라는 것은 dif[i]들을 전부 0으로 만들어야 한다는 소리. 이때 특정한 dif[i] (i>=2)에 영향을 줄 수 있는 연산은 2가지 뿐이고, 2가지중 하나는 dif[i]에 +1이 되고, 나머지 하나는 -1이 되므로 사실상 연산이 고정된다.
따라서 모든 2~n인 i들에 대해서 연산을 시행해주면 된다. 그렇게 되면, 이제 dif[1]에는 어떤 수가 저장되어 있을 것인데, 그것의 절댓값만큼 추가로 연산을 시행해주면 된다.
그리디 문제인데, 차를 보면 사실 연산이 항상 고정되어 있다는 것을 알 수 있다.
#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 1e6 + 100, inf = (ll)1e9 * (ll)1e9 + 7, mod = 1e9 + 7, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
if (!y)return x;
return gcd(y, x % y);
}
void solve() {
cin >> n;
vector<ll>v(n + 1), dif(n + 1);
for (int i = 1; i <= n; i++)cin >> v[i];
for (int i = 1; i <= n; i++) {
dif[i] = v[i] - v[i - 1];
//cout << dif[i] << ' ';
}
ans = 0;
for (int i = 2; i <= n; i++) {
if (dif[i] < 0) {
dif[1] +=dif[i];
ans -= dif[i];
}
else ans += dif[i];
}
ans += abs(dif[1]);
cout << ans;
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> tc;
while (tc--)solve();
}