BZOJ_2802_[Poi2012]Warehouse Store

BZOJ_2802_[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

Sample Output

3
1 2 4

贪心的能满足则满足，插入大根堆里。

否则和堆顶元素比较，如果堆顶元素大就弹出换进来。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

using namespace __gnu_pbds;

typedef long long ll;

#define N 250050

int b[N],ch[N],c[N];

inline bool cmp(const int &x,const int &y) {return b[x]>b[y];}

struct A {

	int b,id;

	bool operator < (const A &x) const {

		return b<x.b;

	}

}a[N];

__gnu_pbds::priority_queue<A>q;

int n;

ll sum;

int main() {

	scanf("%d",&n);

	int i,x,y;

	for(i=1;i<=n;i++) scanf("%d",&c[i]);

	for(i=1;i<=n;i++) scanf("%d",&b[i]);

	for(i=1;i<=n;i++) {

		x=c[i],y=b[i];a[i].b=y; a[i].id=i;

		sum+=x;

		if(sum>=y) {

			sum-=y; q.push(a[i]); ch[i]=1;

		}else {

			if(!q.empty()) {

				if(q.top().b>y) sum=sum+q.top().b-y,ch[q.top().id]=0,q.pop(),q.push(a[i]),ch[i]=1;

			}

		}

		// printf("%lld\n",sum);

	}

	printf("%d\n",q.size());

	for(i=1;i<=n;i++) if(ch[i]) printf("%d ",i);

}

巴特西