这道题，看数据规模就知道至少需要一个 O(nlogn) 的算法。结合题意（题目真的很绕）可知，这道题应该需要一些贪心。现在让我们来分析下。
何时选出的t个人会有最优解呢？我们不妨假设只让甲选t个人，这时，甲一定会选x最大的t个人（y是次要关键字，该怎么排大家应该都清楚）。为了让最终乙也选上这t个人，甲真正选的s个人中剩下的s-t个人的y一定要比这t个人小。既然需要y的大小，我们不妨以y为主要关键字，从大到小排序。 现在问题就变成了，在甲选了t个人后，再在第t个人的后面选s-t个人（在y降序的序列中）。 如果选了t个人后，最后一个人的后面不足s-t个人怎么办？当然是不选最后面的人，而是在1~n-(s-t)个人中找没选的最大的啊。因此我们可以发现——y最小的s-t个人是无论如何也选不进那t个人的（想一想，为什么）。进而我们得到了选出那t个人的正确方法：在前n-(s-t)个人中选出x最大的t个人。 选出后，剩下的s-t个人怎么选呢？我们先找到选出的t个人中下标最大的（注意，现在整个序列以y为关键字降序），然后再对它之后的人排序，选出y最大的s-t个人。 有一个地方的次要关键字容易搞错。题目中要求s-t个人的y值和尽量大，而不是要求t个人中y值和尽量小。因此在以x为主要关键字的那一趟排序中，y应该是降序，而不是升序，这样保证在y降序的序列中t个人中的最后一个人的后面一个的y尽量大。
参考代码
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; #define FOR(i, f, t) for(int i = (f); i <= (t); i++) inline int readIn() { int a; scanf("%d", &a); return a; } const int maxn = 100005; int n,s,t; struct jury { int x; int y; bool cannot; //t bool chosen; //s void input() { x = readIn(); y = readIn(); } } people[maxn]; bool comp1(const jury& a, const jury& b) { return a.y > b.y; //以y为降序的序列中，x不需要排序 } bool comp2(const jury& a, const jury& b) { if(a.cannot != b.cannot) return a.cannot < b.cannot; //选t个人，把最后s-t个人甩后面去 if(a.x != b.x) return a.x > b.x; return a.y > b.y; //这里要让选出的y尽量大 } bool comp3(const jury& a, const jury& b) { if(a.cannot != b.cannot) return a.cannot > b.cannot; //把可能成为那s-t个人的放前面来 if(a.y != b.y) return a.y > b.y; //读题吧。。。 return a.x > b.x; } void run() { n = readIn(); s = readIn(); t = readIn(); FOR(i, 1, n) people[i].input(); std::sort(people + 1, people + 1 + n, comp1); for(int i = n, j = 1; j <= (s - t); j++, i--) people[i].cannot = true; std::sort(people + 1, people + 1 + n, comp2); for(int i = 1; i <= t; i++) people[i].chosen = true; std::sort(people + 1, people + 1 + n, comp1); int maxIndex = 0; for(int i = n; i >= 1; i--) { if(people[i].chosen) { maxIndex = i; break; } } for(int i = maxIndex + 1; i <= n; i++) { people[i].cannot = true; } std::sort(people + 1, people + 1 + n, comp3); for(int i = 1; i <= (s - t); i++) { people[i].chosen = true; } long long ansX = 0; long long ansY = 0; for(int i = 1; i <= n; i++) { if(people[i].chosen) { ansX += people[i].x; ansY += people[i].y; } } cout<<ansX<<" "<<ansY<<endl; } int main() { run(); return 0; }可以说，即使在如今sort满天飞的时代，排序有些时候还是会成为痛点。考试时我用的间接排序，导致sort函数出错，而且我至今都不知道怎么写才是对的。 这是第二次sort函数出错了，第一次是比较函数没写对，这一次也可以算是比较函数出了问题吧。
所以，提出以下要求（勿喷）： 1.尽量使用直接排序 2.对于多个关键字要这样写：
bool operator< (const Struct& b) const { if(a.Major != b.Major) return a.Major < b.Major; return a.Minor < b.Minor; }而不要这样写
bool operator< (const Struct& b) const { if(a.Major == b.Major) return a.Minor < b.Minor; return a.Major < b.Major; }后者如果有很多关键字将会||满天飞。
