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


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';
}