#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
struct fenwick {
int n;
vector<int> bit;
fenwick() {}
fenwick(int n) {
this->n = n + 5;
bit.resize(n + 5);
}
void add(int pos, int val) {
while (pos < n) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
if (pos < 0) return 0;
int ans = 0;
while (pos) {
ans += bit[pos];
pos -= pos & -pos;
}
return ans;
}
int get(int l, int r) {
if (l > r) return 0;
return get(r) - get(l - 1);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), cc;
for (int i = 0; i < n; i++) {
cin >> a[i];
cc.push_back(a[i] + i);
cc.push_back(a[i] - i);
}
sort(all(cc));
cc.erase(unique(all(cc)), cc.end());
int m = cc.size();
auto get_pos = [&](int pos) {
if (pos > cc.back()) return m + 1;
return (int)(upper_bound(all(cc), pos) - cc.begin());
};
int ans = LLONG_MAX;
/*
left : a[j] - (a[i] - (i - j)) = (a[j] - j) - (a[i] - i)
right : a[j] - (a[i] - (j - i)) = (a[j] + j) - (a[i] + i)
*/
/*
Cố định cột i là đỉnh, tìm kiếm tam phân để tìm ra chiều cao tối thiểu chi phí thay đổi
*/
fenwick occ_left(m), sum_left(m), occ_right(m), sum_right(m);
for (int i = 0; i < n; i++) {
int pos = get_pos(a[i] + i);
occ_right.add(pos, 1);
sum_right.add(pos, a[i] + i);
}
auto f = [&](int h, int i) {
int cost = 0;
{
int p = get_pos(h - i);
int k = h - i;
cost += occ_left.get(p) * k - sum_left.get(p);
cost += sum_left.get(p + 1, m) - k * occ_left.get(p + 1, m);
}
{
int p = get_pos(h + i);
int k = h + i;
cost += occ_right.get(p) * k - sum_right.get(p);
cost += sum_right.get(p + 1, m) - k * occ_right.get(p + 1, m);
}
return cost;
};
auto g = [&](int h, int i) {
int cost = 0;
for (int j = 0; j < i; j++) {
cost += abs(a[j] - j - (h - i));
}
for (int j = i; j < n; j++) {
cost += abs(a[j] + j - (h + i));
}
return cost;
};
for (int i = 0; i < n; i++) {
int left_bound = max(i + 1, n - i);
int right_bound = 1e9;
// cout << "POS " << i << '\n';
// for (int j = left_bound; j <= 10; j++) {
// cout << j << ' ' << f(j, i) << ' ' << g(j, i) << '\n';
// }
int l = left_bound, r = right_bound;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (f(mid, i) <= f(mid - 1, i)) l = mid;
else r = mid;
}
ans = min({ans, f(left_bound, i), f(right_bound, i), f(l, i)});
int pos = get_pos(a[i] - i);
occ_left.add(pos, 1);
sum_left.add(pos, a[i] - i);
pos = get_pos(a[i] + i);
occ_right.add(pos, -1);
sum_right.add(pos, -a[i] - i);
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |