Submission #3609456

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = pow(2, 31) - 1;
#define ll long long
#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  int a;
  REP(i, N) {
    cin >> a;
    A[i] = a - i;
  }
  sort(A.begin(), A.end());
  if(A.size() & 1) {
    ll ans = 0;
    REP(i, N) {
      ans += abs(A[i] - A[N / 2]);
    }
    cout << ans << endl;
  } else {
    ll ans = 0;
    REP(i, N) {
      ans += abs(A[i] - A[N / 2]);
    }
    ll ans_cmp = 0;
    REP(i, N) {
      ans_cmp += abs(A[i] - A[N / 2 - 1]);
    }
    ans = min(ans, ans_cmp);
    cout << ans << endl;
  }
  return 0;
}

Submission Info

Judge Result