和poi某題題意化簡后一樣
經典貪心：維護一個大根堆，按T2從小到大，對于每個建筑，若能修好就將它塞進堆里，若不行，和堆頂比一下大小，比堆頂小就把堆頂pop出去把它塞進去
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(ll &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}const int maxn = 310000;struct hea{ ll c; int lc,rc,dist;}tr[maxn]; int tot;int n,rt;struct node{ ll a,b;}a[maxn];bool cmp(node x,node y){ return x.b<y.b; }int newnode(ll c){ tot++; tr[tot].c=c; tr[tot].lc=tr[tot].rc=tr[tot].dist=0; return tot;}int merge(int x,int y){ if(!x||!y) return x|y; if(tr[x].c<tr[y].c) swap(x,y); int k=merge(tr[x].rc,y); if(tr[tr[x].lc].dist<=tr[k].dist) swap(tr[x].lc,k); tr[x].rc=k; tr[x].dist=tr[tr[x].lc].dist+1; return x;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { ll x,y; read(x); read(y); a[i].a=x; a[i].b=y; } sort(a+1,a+n+1,cmp); ll k=0; rt=0; int ans=0; for(int i=1;i<=n;i++) { if(k+a[i].a>a[i].b) { if(tr[rt].c>a[i].a) { k=k-tr[rt].c+a[i].a; rt=merge(tr[rt].lc,tr[rt].rc); rt=merge(rt,newnode(a[i].a)); } } else ans++,k+=a[i].a,rt=merge(rt,newnode(a[i].a)); }新聞熱點
疑難解答
