按照Di排序，从小到大枚举物品，考虑如果直接能选就选上，不能选就考虑替换之前价值最小的来选（显然一定是可行的，只需要在原来选价值最小的时候选这个就行了），这个东西用堆来维护即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct ji{ 4 int d,p; 5 }a[100005]; 6 priority_queue<int>q; 7 int n,m,x,y,s; 8 long long ans; 9 bool cmp(ji x,ji y){ 10 return x.d<y.d; 11 } 12 int main(){ 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++){ 15 scanf("%d%d",&x,&y); 16 if (x>n)ans+=y; 17 else a[++m]=ji{x,y}; 18 } 19 sort(a+1,a+m+1,cmp); 20 for(int i=1;i<=m;i++) 21 if (a[i].d>s){ 22 s++; 23 ans+=a[i].p; 24 q.push(-a[i].p); 25 } 26 else{ 27 if (a[i].p<-q.top())continue; 28 ans+=a[i].p+q.top(); 29 q.pop(); 30 q.push(-a[i].p); 31 } 32 printf("%lld",ans); 33 }