题意：给n(n<=100000)组数，每组数有(a，b),求从这n组数里面选出k(k<=(n/2)+1)组。这k组所有a的和大于剩下n-k组中a的和，并且这k组中所有b的和大于剩下n-k组中b的和。
思路：首先按a排序。对于a[i]，选择a[i]之前没有选择过的或者a[i]总是能>=a[i+1],然后从a[i+2]中开始选择。。这样就可以保证选出来的a的和始终大于另外一半。然后对于可以选择的a，我选择最大的b,这样也可以让选出来的b有一个比它小的对应值。这个值可以通过优先队列来维护。如果n是偶数的话b会少一个对应值。。所以对于n是偶数的情况，最后要多拿出一个值。细节见代码
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; typedef long long ll; int n; struct Node { ll x, y; int id; }; struct Node1 { ll x, y; int id; friend bool operator < (Node1 a, Node1 b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } }; bool cmp(Node a, Node b) { if(a.x==b.x) return a.y > b.y; return a.x > b.x; } bool used[maxn]; Node a[maxn],aa[maxn]; int main() { priority_queue<Node1>q1; scanf("%d",&n); ll sumx = 0, sumy = 0; for(int i=1; i<=n; i++) scanf("%I64d",&aa[i].x); for(int i=1; i<=n; i++) scanf("%I64d",&aa[i].y); for(int i=1; i<=n; i++) { a[i].x=aa[i].x; a[i].y=aa[i].y; a[i].id = i; sumx+=a[i].x; sumy += a[i].y; } sort(a+1,a+1+n,cmp); Node1 b; for(int i=1; i<=n; i+=2) { q1.push((Node1){a[i].x,a[i].y,a[i].id}); used[q1.top().id] = 1; sumx -= q1.top().x*2; sumy -=q1.top().y*2; q1.pop(); q1.push((Node1){a[i+1].x,a[i+1].y,a[i+1].id}); if(sumx < 0&& sumy < 0) break; } if(n%2==0) { used[q1.top().id] = 1; } int cnt = 0,lastnum=0; for(int i=1; i<=n; i++) { if(used[i]) { cnt++; lastnum=i; } } printf("%d ",cnt); for(int i=1; i<=n; i++) { if(used[i]) { printf("%d",i); if(i==lastnum) printf(" "); else printf(" "); } } }