不难，想到优先队列就比较容易做，具体思路见代码注释
也可以使用 重载小于号写到结构体内
如果按能力值排序会比较麻烦一点
#include<cstdio> #include<algorithm> #include<queue> using namespace std; const int N = 1e5+16; struct Node { int d,p;//deadline p是能力值 }node[N]; bool cmp(const Node &A,const Node &B)//按截至时间排序， //如果按能力值排序，在查找空闲时间的时候会增大时间复杂度，需要用到并查集来优化查找 { return A.d<B.d; } int main()//按照排序后 d的时间间隔来确定在优先队列选择几个加入res res表示最大能力值 { int n,i,sum,k,count;//count：间隔 long long res; priority_queue<int> q; while(~scanf("%d",&n)) { sum=0,res=0; for(i=0;i<n;i++) { scanf("%d%d",&node[i].d,&node[i].p); } sort(node,node+n,cmp); if(n==1) { printf("%d\n",node[0].p); continue; } sum=n-1; for(k=sum;k>=0;k--) { if(k-1>=0) { if(node[k].d==node[k-1].d) { q.push(node[k].p); } else { q.push(node[k].p); count=node[k].d-node[k-1].d; while(count!=0&&!q.empty()) { res+=q.top(); q.pop(); count--; } } } else { count=node[0].d; q.push(node[0].p); while(count&&!q.empty()) { res+=q.top(); q.pop(); count--; } } } while(!q.empty()) q.pop(); printf("%lld\n",res); } return 0; }