#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:二分可以正确解这道题吧？只是需要对情况分类讨论，而不只是分为可行与不可行 (1730) Samhammer 2020-11-03 00:25:22
  • Re:二分可以正确解这道题吧？只是需要对情况分类讨论，而不只是分为可行与不可行 (56) Samhammer 2020-11-03 00:26:23