> #include <iostream>
> #include <algorithm>
> using namespace std;
> 
> 
> typedef long long ll;
> 
> const int MAX_N = 100005;
> const int MAX_S = 2000000005;
> 
> struct Cow
> {
> 	int s;
> 	int f;
> 	bool operator < (const Cow & b)const
> 	{
> 		return f < b.f;
> 	}
> }cow[MAX_N];
> 
> int scores[MAX_N];
> 
> int N, C, F;
> 
> int ok(int mid);
> 
> int main()
> {
> 	cin >> N >> C >> F;
> 
> 	for (int i = 0; i < C; i++)
> 	{
> 		cin >> cow[i].s >> cow[i].f;
> 		scores[i] = cow[i].s;
> 	}
> 	sort(cow, cow + C);
> 	sort(scores, scores + C);//枚举所有可能的解并排序
> 
> 	int lb = -1, rb = C, mid;
> 
> 	//先以 解是否偏大 为依据进行二分
> 	while (rb - lb > 1)
> 	{
> 		mid = scores[(lb + rb) >> 1];
> 		if (ok(mid))
> 		{
> 			lb = (lb + rb) >> 1;
> 		}
> 		else
> 		{
> 			rb = (lb + rb) >> 1;
> 		}
> 	}
> 
> 	//最终判断得到的解是否可行
> 	if (lb >= 0)
> 	{
> 		if (ok(scores[lb]) == 2)
> 		{
> 			cout << scores[lb] << '\n';
> 		}
> 		else
> 		{
> 			cout << "-1\n";
> 		}
> 	}
> 	else
> 	{
> 		cout << "-1\n";
> 	}
> 
> 	return 0;
> }
> 
> int ok(int mid)
> {
> 	ll res = 0;
> 	int lb = 0, rb = 0;
> 
> 	for (int i = 0; i < C; i++)
> 	{
> 		if (rb <= (N >> 1) && (cow[i].s >= mid))//先令与 mid 相等的元素归为大于等于 mid
> 		{
> 			rb++;
> 			res += cow[i].f;
> 		}
> 		else if (lb < (N >> 1) && (cow[i].s <= mid))
> 		{
> 			lb++;
> 			res += cow[i].f;
> 		}
> 	}
> 
> 	//对情况分类讨论：
> 
> 	//若 价格大于F 或 大于等于mid 的元素不足 (N + 1) / 2 个, 则断定mid偏大
> 	if (res > F || rb <= (N >> 1))
> 	{
> 		return 0;
> 	}
> 
> 	//若在 价格大于等于mid的元素已达到 (N + 1) / 2 个 的前提下, 价格小于等于mid 的元素不足, 断定mid偏小
> 	if (lb < (N >> 1))
> 	{
> 		return 1;
> 	}
> 
> 	//以上情况均不是, 则 mid 是一个可行解
> 	return 2;
> }

• Re:二分可以正确解这道题吧？只是需要对情况分类讨论，而不只是分为可行与不可行 (56) Samhammer 2020-11-03 00:26:23