[CF] D. Salary Changing - Educational Codeforces Round 75 (Rated for Div. 2)

Solutions Codeforces 贪心二分中位数 1900 Med-

Lastmod: 2025-01-13 周一 00:23:41

https://codeforces.com/contest/1251/problem/D

题目大意

给出奇数 $n \ (< 2 \times 10^5)$ 个人的薪资范围，其中第 $i$ 个人的范围为 $[l_i, r_i] (1 \le l_i \le r_i \le 10^9)$ ，以及薪资和的上限 $\sum l_i \le s \le 2 \times 10^{14}$ 。问当所有人的薪资 $x_i$ 符合自己的范围，且和不超过 $s$ 时，中位数最大可以是多少。

简要题解

乍一想因为我们有的是总薪资的上界，那么这个中位数大概是可以二分的。比如当某个方案中位数是 $x$ 则我们可以通过减少某些 $x$ 的值来得出对于 $x - 1$ 也成立。但是因为下限的存在 $x - 1$ 其实并不是总能达到的，因此我们选择更改一下二分的判断标准，即把二分判断改为，“当我们尝试将中位数设置到 $x$ 时，是否能得出不小于 $x$ 的中位数”。这样一来，就可以二分了。

另一种思考方式是，首先至少我们的中位数不会小于所有位置都选 $l_i$ 的结果 $x_0$ ，显然最优解如果 $x > x_0$ 一定在某些位置不是 $l_i$ ，且这些位置一定为 $x$ 。

判断的过程，对于每一个区间 $[l_i, r_i]$ 若其与 $x$ 不相交，则期望其与中位数无关，则对于它们都会取尽量小的 $l_i$ 使得其他区间有更多的操作空间。

如果我们有超过半数的区间已经严格小于 $x$ 则无论剩下的如何大，都不能使得中位数达到或超过 $x$ 。
若有超过半数的区间严格大于 $x$ 则显然我们已经得到了不差于 $x$ 的结果。
其他情况，说明有一些区间可以取到 $mid$ ，这里我们需要有足够多的值 $>= mid$ 而其他值尽量小，因此让 $l_i$ 最小的一些取 $l_i$ 即可。

复杂度

$T$ ： $O(n \log n \log \max(r_i))$

这里如果先把区间对所有 $l_i$ 排序可以去掉每次二分之后对 $l_i$ 的排序的 $\log n$

$S$ ： $O(n)$

代码实现

 #include <bits/stdc++.h>
using namespace std;
 
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
 
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
 
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }
 
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
 
const int INF = 1e9;
 
void solve() {
  int n;
  LL s; 
  cin >> n >> s;
  vector<int> li(n), ri(n);
  for (int i = 0; i < n; i++) {
    cin >> li[i] >> ri[i];
  }
 
  auto check = [&](int mid) -> bool {
    int cntless = 0, cntmore = 0;
    LL sum = 0;
    vector<int> left;
    for (int i = 0; i < n; i++) {
      if (ri[i] < mid) {
        sum += li[i];
        cntless++;
      } else if (mid < li[i]) {
        sum += li[i];
        cntmore++;
      } else {
        left.push_back(li[i]);
      }
    }
 
    if (cntless >= (n + 1) / 2) return false;
    if (cntmore >= (n + 1) / 2) return true;
    sort(left.begin(), left.end());
    int need = n / 2 - cntless;
    for (int i = 0; i < need; i++) {
      sum += left[i];
    }
    sum += 1LL * (left.size() - need) * mid;
 
    return sum <= s;
  };
 
  int l = 1, r = INF;
  int ans = 1, mid;
 
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
 
  cout << ans << '\n';
}
 
int main() {
  int t = 1; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Prev: [CF] B. Two Cakes - Educational Codeforces Round 35 (Rated for Div. 2)
Next: [CF] C. Minimize The Integer - Educational Codeforces Round 75 (Rated for Div. 2)

Gitalking ...

	#include <bits/stdc++.h>
	using namespace std;

	int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

	using LL = long long;
	using ULL = unsigned long long;
	using LD = long double;
	using PII = pair<int, int>;
	using VI = vector<int>;
	using MII = map<int, int>;

	template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
	template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
	template<typename T> bool ckmin(T &x,const T &y) {
	return y<x ? (x=y, true) : false; }
	template<typename T> bool ckmax(T &x,const T &y) {
	return x<y ? (x=y, true) : false; }
	template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
	if(z<x) { y=x; x=z; } else if(z<y) y=z; }
	template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
	if(x<z) { y=x; x=z; } else if(y<z) y=z; }

	// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
	// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

	/*
	---------1---------2---------3---------4---------5---------6---------7---------
	1234567890123456789012345678901234567890123456789012345678901234567890123456789
	*/

	const int INF = 1e9;

	void solve() {
	int n;
	LL s;
	cin >> n >> s;
	vector<int> li(n), ri(n);
	for (int i = 0; i < n; i++) {
	cin >> li[i] >> ri[i];
	}

	auto check = [&](int mid) -> bool {
	int cntless = 0, cntmore = 0;
	LL sum = 0;
	vector<int> left;
	for (int i = 0; i < n; i++) {
	if (ri[i] < mid) {
	sum += li[i];
	cntless++;
	} else if (mid < li[i]) {
	sum += li[i];
	cntmore++;
	} else {
	left.push_back(li[i]);
	}
	}

	if (cntless >= (n + 1) / 2) return false;
	if (cntmore >= (n + 1) / 2) return true;
	sort(left.begin(), left.end());
	int need = n / 2 - cntless;
	for (int i = 0; i < need; i++) {
	sum += left[i];
	}
	sum += 1LL * (left.size() - need) * mid;

	return sum <= s;
	};

	int l = 1, r = INF;
	int ans = 1, mid;

	while (l <= r) {
	mid = (l + r) >> 1;
	if (check(mid)) {
	ans = mid;
	l = mid + 1;
	} else {
	r = mid - 1;
	}
	}

	cout << ans << '\n';
	}

	int main() {
	int t = 1;
	cin >> t;
	while (t--) {
	solve();
	}
	return 0;
	}