题目大意

现在有 \(n\) 个石子，第 \(i\) 个石子贡献为 \((x_i,y_i)\)，甲要从这选出 \(s\) 个石子，乙会从甲选出的石子中选 \(t\) 个石子，乙会先使得他选的 \(t\) 个石子的 \(y\) 值最大，再使得 \(t\) 个石子的 \(x\) 值最小。

请问甲要选哪 \(s\) 个石子可先使得乙选的石子的 \(x\) 值最大，未选中的 \(s-t\) 个石子的 \(y\) 值最大，输出这两个选的 \(s\) 个石子的 \(x\) 值和 \(y\) 值之和。

对于 \(100\%\) 的测试数据 \(n \leq 100000, x, y \leq 1000000\)。

解题思路

首先，全部按 \(y\) 值从大到小排序。

然后，将前 \(n-s+t\) 按 \(x\) 值从大到小排序。

咕咕咕。。。

AC CODE

#include <bits/stdc++.h>

using namespace std;

#define int long long

int read()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

void write(int x)
{
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

#define _ 100007

int n, s, t;

struct abc
{
	int x, y, id;
} k[_];

bool cmp(abc a, abc b)
{
	if(a.y == b.y) return a.x > b.x;
	return a.y > b.y;
}

bool cmmp(abc a, abc b)
{
	if(a.x == b.x) return a.id < b.id;
	return a.x > b.x;
}

int maxid, ans1, ans2;

signed main()
{
	n = read();
	s = read();
	t = read();
	for(int i = 1; i <= n; ++i)
	{
		k[i].x = read();
		k[i].y = read();
	}
	sort(k + 1, k + n + 1, cmp);
	for(int i = 1; i <= n; ++i) k[i].id = i;
	sort(k + 1, k + n - s + t + 1, cmmp);
	for(int i = 1; i <= t; ++i)
	{
		ans1 += k[i].x;
		ans2 += k[i].y;
		maxid = max(maxid, k[i].id);
	}
	sort(k + 1, k + n + 1, cmp);
	for(int i = 1; i <= s - t; ++i)
	{
		ans1 += k[maxid + i].x;
		ans2 += k[maxid + i].y;
	}
	write(ans1);
	putchar(' ');
	write(ans2);
	putchar('\n');
	return 0;
}