首页 > 代码库 > bzoj2802 [Poi2012]Warehouse Store
bzoj2802 [Poi2012]Warehouse Store
Description
有一家专卖一种商品的店，考虑连续的n天。
第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。
如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。
Input
第一行一个正整数n (n<=250,000)。
第二行n个整数A1,A2,...An (0<=Ai<=10^9)。
第三行n个整数B1,B2,...Bn (0<=Bi<=10^9)。
Output
第一行一个正整数k，表示最多能满足k个顾客的需求。
第二行k个依次递增的正整数X1,X2,...,Xk，表示在第X1,X2,...,Xk天分别满足顾客的需求。
Sample Input
6
2 2 1 2 1 0
1 2 2 3 4 4
2 2 1 2 1 0
1 2 2 3 4 4
Sample Output
3
1 2 4
1 2 4
啊……我要开始疯狂地写stl堆了
对于第i天的货物，它们只可能在第i到第n天用上
可以考虑倒序处理，每次把当前的b[i]扔进堆中，然后提取出当前堆中的最小b[k]，把a[i]给它。如果货物还有剩的就继续搞
因为倒序处理完序号有点乱还wa了一次……
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define N 250010using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}priority_queue<pa,vector<pa>,greater<pa> >q;int n;int a[N],b[N],ans;bool num[N];int main(){ n=read(); for (int i=n;i>=1;i--)a[i]=read(); for (int i=n;i>=1;i--)b[i]=read(); while (!q.empty())q.pop(); for (int i=1;i<=n;i++) { q.push(make_pair(b[i],n-i+1)); while (a[i]&&!q.empty()) { int f=q.top().first,rnk=q.top().second; q.pop(); if (a[i]>=f) { num[rnk]=1; ans++; a[i]-=f; }else { q.push(make_pair(f-a[i],rnk)); a[i]=0; } } } printf("%d\n",ans); for (int i=1;i<=n;i++) if (num[i])printf("%d ",i); return 0;}
bzoj2802 [Poi2012]Warehouse Store
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。