很经典的贪心，有两种做法 1：我的做法，按需求从小到大排序，写一棵线段树，对于每个判这一天是否能取，易证这样取一定是最优的 2：经典做法？直接按天数处理，维护一个大根堆，如果当前这一天不能满足顾客要求，若大根堆堆顶比当前要求大，就把堆顶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 long#define lowbit(x) x&(-x)using namespace std;void read(int &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 = 260000;struct node{ int x,i; node(){} node(int _x,int _i){x=_x;i=_i;}}a[maxn]; int n;bool cmp(node x,node y) {return x.x<y.x;}ll v[maxn];struct tree{ ll c,flag;}tr[maxn<<2];void pushup(int x){ int lc=x<<1,rc=lc|1; tr[x].c=min(tr[lc].c,tr[rc].c);}void pushdown(int x){ if(!tr[x].flag) return ; int lc=x<<1,rc=lc|1; tr[lc].flag+=tr[x].flag; tr[lc].c-=tr[x].flag; tr[rc].flag+=tr[x].flag; tr[rc].c-=tr[x].flag; tr[x].flag=0;}void build_tree(int x,int l,int r){ if(l==r){ tr[x].c=v[l]; return ; } int mid=(l+r)>>1,lc=x<<1,rc=lc|1; build_tree(lc,l,mid); build_tree(rc,mid+1,r); pushup(x);}void change(int x,int l,int r,int lx,int rx,ll c){ if(lx<=l&&r<=rx) { tr[x].c-=c; tr[x].flag+=c; return ; } int mid=(l+r)>>1,lc=x<<1,rc=lc|1; pushdown(x); if(rx<=mid) change(lc,l,mid,lx,rx,c); else if(lx>mid) change(rc,mid+1,r,lx,rx,c); else change(lc,l,mid,lx,mid,c),change(rc,mid+1,r,mid+1,rx,c); pushup(x);}ll query(int x,int l,int r,int lx,int rx){ if(lx<=l&&r<=rx) return tr[x].c; pushdown(x); int mid=(l+r)>>1,lc=x<<1,rc=lc|1; if(rx<=mid) return query(lc,l,mid,lx,rx); else if(lx>mid) return query(rc,mid+1,r,lx,rx); else return min(query(lc,l,mid,lx,mid),query(rc,mid+1,r,mid+1,rx));}int ans[maxn];int main(){ read(n); for(int i=1;i<=n;i++) { int x; read(x); v[i]=v[i-1]+x; } build_tree(1,1,n); for(int i=1;i<=n;i++) { int x; read(x); a[i]=node(x,i); } sort(a+1,a+n+1,cmp); int an=0; for(int i=1;i<=n;i++) { ll k=query(1,1,n,a[i].i,n); if(k>=a[i].x) ans[++an]=a[i].i,change(1,1,n,a[i].i,n,a[i].x); } sort(ans+1,ans+an+1); PRintf("%d/n",an); for(int i=1;i<an;i++) { printf("%d ",ans[i]); } printf("%d/n",ans[an]); return 0;}新闻热点
疑难解答
