分析:一开始差点看错题了。。
这题我觉得挺不错,,我没有一眼切有点不应该。。堆的应用还不是很熟练啊。。
这个的话,我们按照时间排序,然后每次直接添加进小根堆,如果当前时间小于已经添加的数量,那么明显说明我们要在已经添加的任务中空出来一个位置,那么由于是小根堆,每次添加会自动把最小的放到堆顶,那么我们每次如果有这种情况直接把堆顶拿出来就好了。
#include <iostream>#include <cstring>#include<cstdio>#include<algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;typedef long long ll;int n,m;const int N=1e5+5;struct node{ int t,v;}a[N];ll ans;int heap[N],sz;bool cmp(node a,node b){ return a.t<b.t;}inline void put(node x){ ans+=x.v; heap[++sz]=x.v; int now=sz; while(now>1&&heap[now>>1]>heap[now]) { swap(heap[now],heap[now>>1]); now>>=1; }}inline void pop(){ ans-=heap[1]; heap[1]=heap[sz--]; int x=1; while (x<=(sz>>1)) { int next=x<<1; if (next<sz&&heap[next|1]<heap[next])next++; if (heap[next]>heap[x])return; swap(heap[next],heap[x]); x=next; }}int main(){ scanf("%d",&n); fo(i,1,n) { scanf("%d%d",&a[i].t,&a[i].v); } sort(a+1,a+1+n,cmp); int tim=0; fo(i,1,n) { put(a[i]);tim++; if (tim>a[i].t) { pop(); tim--; } } printf("%lld\n",ans); return 0;}