Hello! I was trying to solve this problem and couldn’t really find any working solution. I thought of a bunch of things and one of them was finding the median of the array and making everything before it increasing and <= than it and everything after it increasing and >= than it. This didn’t work in the fifth and seventh test. There were some other things I thought but I came up with counter cases for those so I don’t think it’s worth mentioning those.
Here’s the code for it.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
long long a[N], b[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b, b + n);
long long median = b[n / 2];
int pos;
for (int i = 0;; ++i)
if (a[i] == median) {
pos = i;
break;
}
long long res = 0;
for (int i = 0; i < pos; ++i) {
if (a[i] > median) {
res += a[i] - median;
a[i] = median;
}
if (a[i] > a[i + 1]) {
res += a[i] - a[i + 1];
a[i] = a[i + 1];
}
}
for (int i = pos; i < n - 1; ++i) {
if (a[i] > a[i + 1]) {
res += a[i] - a[i + 1];
a[i] = a[i + 1];
}
}
cout << res;
}
Would appreciate any hints!
Problem Link