【BZOJ4946】[NOI2017]蔬菜（贪心）

题面

题解

忽然发现今年\(NOI\)之前的时候切往年\(NOI\)的题目，就\(2017\)年的根本不知道怎么下手（一定是我太菜了）

这题是一道神仙题（下定义），然而部分分多得不得了，不知道写一个费用流可以得多少分。

我决定先强行插入一下费用流的做法，费用流是这样子的：首先对于蔬菜拆点，每一天拆出一个点，因为蔬菜可以购买的量逐渐递减，因此每一天向下一天连接流量为当前天减少\(d\)的边，费用为\(0\)，然后考虑把蔬菜卖出去，那么就是从一个蔬菜拆出来的某一天向汇点连边，因为限制每天购买的总量，所以再对于每一天的购买的蔬菜拆一个点，然后这一天的每一个蔬菜向这个点连容量为\(inf\)，费用为蔬菜费用的边，再从这个点向汇点连容量为\(m\)，费用为\(0\)的边。显然源点向每个蔬菜的第一天连容量为蔬菜数量，费用为\(0\)的边，至于第一次购买产生的额外贡献，我们把连的那条边拆出一个单位来，再额外链接一下容量为\(1\)，费用为第一次购买产生的额外贡献的边。这样子连边就好了（应该是对的）。

跳出来，往正解的方面想。

显然不难发现一个\(O(nQ)\)的贪心，蔬菜会逐渐减少很不好做，我们倒过来，反过来考虑每一天，那么蔬菜的数量变成了每一天都增加每种蔬菜一定量，然后我们需要倒着买蔬菜就好了。可能需要数据结构什么的维护一下，但是大致的复杂度就是上述的东西。

我们现在再正着考虑，假设我们知道我们在\(p\)天的时候的最优解中，买了哪些蔬菜，那么我们可以很容易的得到\(p-1\)天的答案，显然只需要把利润最小的那\(m\)个蔬菜给去掉就好了，因为第\(p-1\)天可以购买的蔬菜不会少于第\(p\)天，在第\(p\)天能够买到的，在\(p-1\)天也一定能够买到。

前面说的不是很清楚，现在考虑如何求解第\(p\)天的答案。我们既然是增加蔬菜，那么这个操作很容易维护，只需要搞一个堆出来，然后每次把当前所拥有的所有蔬菜全部拿出来贪心取就好了，稍微注意一下第一次选产生的额外贡献的细节就好。然后考虑如何递推回去，还是拿一个堆维护，同理注意一下第一次选产生的额外贡献。

既然这么讲了贪心怎么写，是不是觉得其实这就是一个模拟费用流的过程啊，倒推回去就是一个退流的过程，正推的贪心，显然每天只有那么几条路径，用堆维护等价于跑费用流，忽然感觉很妙啊。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 100100

#define pb push_back

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Node{int v,i;}S[MAX];

bool operator<(Node a,Node b){return a.v<b.v;}

int P=1e5,top,sum;

int n,m,Qry,a[MAX],s[MAX],c[MAX],x[MAX],used[MAX];

ll ans[MAX];

bool vis[MAX];

vector<int> d[MAX];

priority_queue<Node> Q;

int main()

{

	n=read();m=read();Qry=read();

	for(int i=1;i<=n;++i)a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read();

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

		if(!x[i])d[P].pb(i);

		else d[min(P,(c[i]+x[i]-1)/x[i])].pb(i);

	for(int i=P;i;--i)

	{

		for(int j=0,l=d[i].size();j<l;++j)

			Q.push((Node){a[d[i][j]]+s[d[i][j]],d[i][j]});

		if(Q.empty())continue;

		for(int j=m;j&&!Q.empty();)

		{

			Node u=Q.top();Q.pop();

			if(!vis[u.i])

			{

				vis[u.i]=true;ans[P]+=u.v;used[u.i]+=1;--j;

				if(c[u.i]>1)Q.push((Node){a[u.i],u.i});

			}

			else

			{

				int rest=min(j,c[u.i]-used[u.i]-(i-1)*x[u.i]);

				ans[P]+=1ll*rest*u.v;used[u.i]+=rest;j-=rest;

				if(used[u.i]!=c[u.i])S[++top]=(Node){a[u.i],u.i};

			}

		}

		while(top)Q.push(S[top--]);

	}

	while(!Q.empty())Q.pop();

	for(int i=1;i<=n;++i)sum+=used[i];

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

		if(used[i]==1)Q.push((Node){-s[i]-a[i],i});

		else if(used[i])Q.push((Node){-a[i],i});

	for(int i=P-1;i;--i)

	{

		ans[i]=ans[i+1];

		while(sum>i*m&&!Q.empty())

		{

			Node u=Q.top();Q.pop();u.v*=-1;

			if(used[u.i]>1)

			{

				int rest=min(sum-i*m,used[u.i]-1);

				used[u.i]-=rest;sum-=rest;ans[i]-=1ll*rest*u.v;

				if(used[u.i]==1)Q.push((Node){-a[u.i]-s[u.i],u.i});

				else Q.push((Node){-a[u.i],u.i});

			}

			else --sum,--used[u.i],ans[i]-=u.v;

		}

	}

	while(Qry--)printf("%lld\n",ans[read()]);

	return 0;

}

巴特西

【BZOJ4946】[NOI2017]蔬菜（贪心）

【BZOJ4946】[NOI2017]蔬菜（贪心）

题面

题解

最新文章

热门文章