10
15
2015
0

2802: [Poi2012]Warehouse Store

2802: [Poi2012]Warehouse Store

Time Limit: 10 Sec  Memory Limit: 64 MBSec  Special Judge
Submit: 231  Solved: 119
[Submit][Status][Discuss]

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

HINT

 

Source

   贪心题。。。因为题目要求是满足要求的人数最多而不是收获价值最多。。所以我们先对于每一天判断当前的剩余是否足够。。如果足够就满足顾客要求。。如果不够就去之前的时间中找到需求最多的一天然后替换。。这样满足要求的人数不变但是库存增加了。。

   然后找最大可以用堆维护。。。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 250010;
struct data{ll val,id;} t;
bool operator < (data a,data b){return a.val<b.val;}
priority_queue <data> heap;
ll n,a[N],b[N],now,ans[N],tot;
ll read(){
	ll x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int main(){
	n = read();
	for (ll i=1;i<=n;i++) a[i] = read();
	for (ll i=1;i<=n;i++) b[i] = read();
	for (ll i=1;i<=n;i++){
		now+=a[i];
		if (now>=b[i]) {
			now-=b[i];heap.push((data){b[i],i});
			ans[i] = 1;
		}
		else if (!heap.empty()){
			t = heap.top();
			if (t.val>b[i]) heap.pop(),ans[t.id] = 0,ans[i] = 1,now+=t.val-b[i],heap.push((data){b[i],i});
		}
	}
	for (ll i=1;i<=n;i++) if (ans[i]) tot++;
	printf("%d\n",tot);
	for (ll i=1;i<=n;i++) if (ans[i]) printf("%d ",i);
}
Category: BZOJ题解 | Tags: | Read Count: 310

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com