Poi2012 Warehouse Store

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Fri Sep 21 17:54:17 CST 2018

In Category: NoCategory

Description：

每天上午得到 $a_i$ 件，下午可以选择卖出 $b_i$ 件，问最多能满足几个。

$1\le n \le 250000$

Solution：

贪心能卖则卖，用一个大根堆来维护可以撤销的方案。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 250010

int a[MAXN],b[MAXN];

int main()

{

	scanf("%d",&n);

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

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

	long long cur = 0;

	priority_queue< pair<int,int> > q;

	int ans = 0;

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

	{

		cur += a[i];

		if(cur >= b[i])

		{

			q.push(make_pair(b[i],i));

			cur -= b[i];

			++ans;

		}

		else

		{

			if(!q.empty() && b[i] < q.top().first)

			{

				cur += q.top().first;q.pop();

				cur -= b[i];

				q.push(make_pair(b[i],i));

			}

		}

	}

	cout << ans << endl;

	priority_queue<int> res;

	while(!q.empty())

	{

		res.push(-q.top().second);q.pop();

	}

	while(!res.empty())

	{

		cout << -res.top() << " ";

		res.pop();

	}

	cout << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051