# 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 %lld\n", 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';}`