1244E - Minimizing Difference - CodeForces Solution

binary search constructive algorithms greedy sortings ternary search two pointers *2000

Please click on ads to support us..

Python Code: 

from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = defaultdict(lambda : 0)
for i in a:
    cnt[i] += 1
s = list(cnt.keys())
s.sort()
l, r = 0, len(s) - 1
mi, ma = s[l], s[r]
while l ^ r and k:
    if cnt[mi] <= cnt[ma]:
        c = min((s[l + 1] - mi) * cnt[mi], k)
        mi += c // cnt[mi]
        k -= c
        l += 1
        cnt[s[l]] += cnt[s[l - 1]]
    else:
        c = min((ma - s[r - 1]) * cnt[ma], k)
        ma -= c // cnt[ma]
        k -= c
        r -= 1
        cnt[s[r]] += cnt[s[r + 1]]
ans = ma - mi
print(ans)

C++ Code: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 1e5+1, INF = 1e18;
ll n, k, arr[N], pref[N];

bool val(ll x) {
	ll res = INF;

	// i = min, j = max
	for (int i = 1, j = 1; i <= n; i++) {
		while (j+1 <= n && arr[j+1] - arr[i] <= x) {
			j++;
		}
		res = min(res, arr[i] * i - pref[i] + pref[n] - pref[j] - (arr[i] + x) * (n - j));
	}

	// i = max, j = min
	for (int i = 1, j = 1; i <= n; i++) {
		while (arr[i] - arr[j] > x) {
			j++;
		}
		res = min(res, pref[n] - pref[i] - arr[i] * (n - i) + (arr[i] - x) * (j - 1) - pref[j - 1]);
	}

	return res <= k;
}

int main() {
    cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	sort(arr+1, arr+n+1);
	for (int i = 1; i <= n; i++) {
		pref[i] = pref[i-1] + arr[i];
	}
	
	ll lo = 0, hi = INF;
	while (lo <= hi) {
		ll mid = (lo + hi)/2;
		if (val(mid)) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}

	cout << lo << " " << endl;
}


Comments

Submit
0 Comments
More Questions

1047B - Cover Points
1381B - Unmerge
1256A - Payment Without Change
908B - New Year and Buggy Bot
979A - Pizza Pizza Pizza
731A - Night at the Museum
742A - Arpa’s hard exam and Mehrdad’s naive cheat
1492A - Three swimmers
1360E - Polygon
1517D - Explorer Space
1230B - Ania and Minimizing
1201A - Important Exam
676A - Nicholas and Permutation
431A - Black Square
474B - Worms
987B - High School Become Human
1223A - CME
1658B - Marin and Anti-coprime Permutation
14B - Young Photographer
143A - Help Vasilisa the Wise 2
320A - Magic Numbers
1658A - Marin and Photoshoot
514A - Chewbaсca and Number
382A - Ksenia and Pan Scales
734B - Anton and Digits
1080A - Petya and Origami
1642D - Repetitions Decoding
1440A - Buy the String
1658F - Juju and Binary String
478A - Initial Bet