NOI2017 蔬菜 题解

First Post:

Last Update:

题意： https://loj.ac/p/2306

非常好题目，VP 时只会 60，其实再思考一下应该就会 80 了。

首先，蔬菜变质是个非常难以处理的问题，你一边卖菜还要考虑之后会不会变质，不如将时间倒流，变为从某个时刻开始，每天进货若干单位的蔬菜。这个进货量是和你的销售无关的，所以在每个时刻，你只需选择当前有的，价格最大的 单位蔬菜卖出即可。用堆维护，每次暴力实现进货过程，即可在 时间内解决单次询问，拿到 分的高分。

考虑优化做法，发现卖菜的过程和每种菜进货的第一天（也就是 原问题中每种菜的 deadline) 都不是复杂度瓶颈。主要问题是每天要把已经进货的菜的个数加上 ，这很麻烦。

我们发现这个过程其实完全没有必要，因为你买不买菜和进货数量也没有很强的关系，你也只关心当前有没有这种菜。所以你完全可以只用一个优先队列维护当前拥有的菜，再用一个数组维护每种菜当前卖掉的数量，这样每个时刻，堆顶每种菜拥有的数量都是可以计算的。直接做就行。

分代码部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ll Brute(int tim)
{
	ll ans = 0;
	while(!pq.empty()) pq.pop();
	for(int i = 1;i <= n;i++) usd[i] = 0;
	for(int i = Lim;i >= 1;i--) //Lim = 100000
	{
		for(auto it : P[i])
			pq.emplace(a[it] + s[it],it);
		if(i > tim) continue;
		vector<node> stk;
		for(int now = m;now && pq.size();)
		{
			node tmp = pq.top();pq.pop();
			if(usd[tmp.id] == 0)
			{
				ans += tmp.c;usd[tmp.id]++;now--;
				if(c[tmp.id] > 1) pq.emplace(a[tmp.id],tmp.id);
			}
			else
			{
				int dta = min(now,c[tmp.id] - usd[tmp.id] - (i - 1) * x[tmp.id]);
				ans += 1ll * dta * tmp.c;usd[tmp.id] += dta;now -= dta;
				if(usd[tmp.id] < c[tmp.id]) stk.push_back(tmp);
			}
		}
		while(stk.size()) pq.push(stk.back()),stk.pop_back();
	}
	return ans;
}

考虑 分怎么写，我们需要对每个天数求出答案。发现 和 之间其实只差了一点：就是我们要少卖 单位菜。那假设我们已经获得了 的解，在求解 时，如果当前卖掉的菜不多于 ，就不用管，否则我们需要撤销一道已经卖出去的菜。选择价格最小的菜撤销即可。这其实就是一种反悔贪心。

上文我们没有提到 “第一次卖菜获得 收益” 如何处理，其实这是简单的，在第一次进货时，将 加入堆中，如果这道菜被卖出去了，就弹出 ，加入 即可。撤销也是类似的，在这道菜被撤销到只剩一个单位时，将 加入小根堆中即可。

如果从模拟费用流的视角来理解这道题，那最后 分恰恰相当于一个退流的过程，这再一次说明了模拟费用流和反悔贪心之间的紧密联系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 1e5 + 5,Lim = 1e5;
int n,m,Q;
int a[N],s[N],c[N],x[N];

struct node{
	int c,id; 
	node(){}
	node(const int _c,const int _id): c(_c),id(_id) {}
	bool operator < (const node &rhs) const { return c < rhs.c;}
};
priority_queue<node> pq;
vector<int> P[N];
inline void Prework()
{
	read(n);read(m);read(Q);
	for(int i = 1;i <= n;i++) read(a[i]),read(s[i]),read(c[i]),read(x[i]);
	for(int i = 1;i <= n;i++)
	{
		if(x[i] > 0)
		{
			int tim = (c[i] + x[i] - 1) / x[i];
			P[min(tim,Lim)].push_back(i);
		}
		else P[Lim].push_back(i);
	}	
}
int usd[N]; // 用掉了多少
ll ans[N];
ll Brute(int tim)
{
	ll ans = 0;
	while(!pq.empty()) pq.pop();
	for(int i = 1;i <= n;i++) usd[i] = 0;
	for(int i = Lim;i >= 1;i--)
	{
		for(auto it : P[i])
			pq.emplace(a[it] + s[it],it);
		if(i > tim) continue;
		vector<node> stk;
		for(int now = m;now && pq.size();)
		{
			node tmp = pq.top();pq.pop();
			if(usd[tmp.id] == 0)
			{
				ans += tmp.c;usd[tmp.id]++;now--;
				if(c[tmp.id] > 1) pq.emplace(a[tmp.id],tmp.id);
			}
			else
			{
				int dta = min(now,c[tmp.id] - usd[tmp.id] - (i - 1) * x[tmp.id]);
				ans += 1ll * dta * tmp.c;usd[tmp.id] += dta;now -= dta;
				if(usd[tmp.id] < c[tmp.id]) stk.push_back(tmp);
			}
		}
		while(stk.size()) pq.push(stk.back()),stk.pop_back();
	}
	return ans;
}
int main()
{
	Prework();
	ans[Lim] = Brute(Lim);
	while(!pq.empty()) pq.pop();
	for(int i = 1;i <= n;i++)
		if(usd[i] == 1) pq.emplace(-a[i] - s[i],i);
		else if(usd[i] > 0) pq.emplace(-a[i],i);
	ll sum = 0;
	for(int i = 1;i <= n;i++) sum += usd[i];
	for(int i = Lim - 1;i >= 1;i--)
	{
		ans[i] = ans[i + 1];
		while(sum > i * m && pq.size())
		{
			node tmp = pq.top();
			tmp.c *= -1;
			if(usd[tmp.id] > 1)
			{
				int dta = min(sum - 1ll * i * m,(ll)usd[tmp.id] - 1);
				usd[tmp.id] -= dta;ans[i] -= 1ll * dta * tmp.c;
				sum -= dta;
				if(usd[tmp.id] == 1) pq.pop(),pq.emplace(-a[tmp.id]-s[tmp.id],tmp.id);
			}
			else ans[i] -= tmp.c,usd[tmp.id]--,sum--,pq.pop();
		}
	}
	for(int _ = 1,x;_ <= Q;_++)
		read(x),write(ans[x]);
	return 0;
}
≡