Description：

有 $n$ 个人，每个人有两个属性 $x_i$ 和 $y_i$ ，现在甲从这 $n$ 个人中挑 $s$ 个人，乙从这 $s$ 个人中挑 $t$ 个人，甲想让这 $t$ 个人 $x$ 属性之和最大，同时 $y$ 之和最小，乙相反，问怎样选能使 $x$ 属性之和最大，在此基础上 $s-t$ 个人 $y$ 属性最大，在此基础上 $s$ 的 $x$ 最大，输出 $x$ 和 $y$ 属性之和。

$1\le n \le 100000$

Solution：

显然按 $y_i$ 排序的后 $s-t$ 个一定不会被选到最终的答案里，而其他的都有可能，于是就按 $y_i$ 从小到大排序， $y$ 相同时按 $x$ 从大到小排序，去掉最后的 $s-t$ 个，在去掉后的数组中选出 $x$ 最大时 $y$ 最大的 $t$ 个作为最终的答案，之所以选 $y$ 最大是因为要让 $s-t$ 那些人的 $y$ 最大，这些 $y$ 一定都小于 $t$ 的 $y$ ，问题就变成了构造一种方案使得这 $t$ 个能被取为最终的答案，发现只有 $y_i\le y_k$ 的人可能被乙排掉，于是就再把剩下的按 $y$ 排序，选 $y_i\le y_k$ 中 $y$ 最大的就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,s,t;

#define MAXN 100010

struct peo{int x,y,tag;}p[MAXN];

bool cmp_maxy_maxx(peo a,peo b){return (a.y == b.y ? a.x > b.x : a.y > b.y);}

bool cmp_miny_maxx(peo a,peo b){return (a.y == b.y ? a.x > b.x : a.y < b.y);}

bool cmp_minx_maxy(peo a,peo b){return (a.x == b.x ? a.y > b.y : a.x < b.x);}

bool cmp_miny_minx(peo a,peo b){return (a.y == b.y ? a.x < b.x : a.y < b.y);}

bool cmp_minx_miny(peo a,peo b){return (a.x == b.x ? a.y < b.y : a.x < b.x);}

int main()

{

	scanf("%d%d%d",&n,&s,&t);

	for(int i = 1;i <= n;++i)scanf("%d%d",&p[i].x,&p[i].y);

	sort(p + 1,p + 1 + n,cmp_miny_maxx);

	sort(p + 1 + s - t,p + 1 + n,cmp_minx_miny);

	long long sumx = 0,sumy = 0;

	for(int i = 1;i <= t;++i)

	{

		sumx += p[n - i + 1].x;

		sumy += p[n - i + 1].y;

		p[n - i + 1].tag = 1;

	}

	sort(p + 1,p + 1 + n,cmp_miny_minx);

	int pos;

	for(pos = 1;pos <= n && p[pos + 1].tag != 1;++pos);

	for(int i = pos;i >= pos - (s - t) + 1;--i)

	{

		sumx += p[i].x;

		sumy += p[i].y;

	}

	cout << sumx << " " << sumy << endl;

	return 0;

}