HackerEarth Capitals and cities problem solution

In this HackerEarth Capitals and cities problem solution Suppose we have n cities with integer coordinate on a line. First, we have to select a city to be the capital. Then in each operation, we have to choose a non-capital city and change it’s coordinate by 1 (-1 or +1). We have to pick the capital and do the operations exactly k time so that the sum of distances from cities to the capital is minimized. Print the index of the selected capital and the desired sum after exactly k operations. If there are multiple such choices, output the smallest index of an optimal capital.

You are required to print the index of the selected capital and required sum after k operations. If there are multiple such choices, print the smallest index of an optimal capital.

HackerEarth Capitals and cities problem solution.

#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, k, id = N, A[N], P[N];
long long tot, Mn = LLONG_MAX;
bool CMP(int i, int j) {return (A[i] < A[j]);}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]), P[i] = i;
    sort(P + 1, P + n + 1, CMP);
    for (int i = 1; i <= n; i++)
        tot += A[P[i]] - A[P[1]];
    for (int i = 1; i <= n; i++)
    {
        if (tot >= k && Mn > tot - k)
            Mn = tot - k, id = P[i];
        if (tot >= k && Mn >= tot - k)
            Mn = tot - k, id = min(id, P[i]);
        if (tot < k && Mn > ((k - tot) & 1))
            Mn = (k - tot) & 1, id = P[i];
        if (tot < k && Mn >= ((k - tot) & 1))
            Mn = (k - tot) & 1, id = min(id, P[i]);
        tot += (A[P[i + 1]] - A[P[i]]) * 1LL * (i + i - n);
    }
    return !printf("%d %lldn", id, Mn);
}

second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 14;

int n, k;
pair<int, int> a[maxn];
ll suf[maxn];
int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n; i++)
    cin >> a[i].first, a[i].second = i;
  sort(a, a + n);
  for(int i = n - 1; i >= 0; i--)
    suf[i] = suf[i + 1] + a[i].first;
  ll pre = 0, ans = 1e18;
  int cer;
  for(int i = 0; i < n; i++){
    ll me = (ll) i * a[i].first - pre + suf[i + 1] - (ll) (n - i - 1) * a[i].first - k;
    me = max(0ll, me);
    if(((ll) i * a[i].first - pre + suf[i + 1] - (ll) (n - i - 1) * a[i].first - k) % 2)
        me = max(me, 1ll);
    if(me < ans || ans == me && cer > a[i].second){
      ans = me;
      cer = a[i].second;
    }
    pre += a[i].first;
  }
  cout << cer + 1 << ' ' << ans << 'n';
}

coding problems solutions