【Codeforces】CF 2014 G

Milky Days

题目描述

Little John is as little as night is day — he was known to be a giant, at possibly $2.1$ metres tall. It has everything to do with his love for milk.

His dairy diary has $n$ entries, showing that he acquired $a_i$ pints of fresh milk on day $d_i$. Milk declines in freshness with time and stays drinkable for a maximum of $k$ days. In other words, fresh milk acquired on day $d_i$ will be drinkable between days $d_i$ and $d_i+k-1$ inclusive.

Every day, Little John drinks drinkable milk, up to a maximum of $m$ pints. In other words, if there are less than $m$ pints of milk, he will drink them all and not be satisfied; if there are at least $m$ pints of milk, he will drink exactly $m$ pints and be satisfied, and it’s a milk satisfaction day.

Little John always drinks the freshest drinkable milk first.

Determine the number of milk satisfaction days for Little John.

输入格式

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$), the number of test cases.

The first line of each test case consists of three integers $n$, $m$, $k$ ($1\le n$, $m$, $k\le 10^5$), the number of diary entries, the maximum pints needed for a milk satisfaction day, and the duration of milk’s freshness.

Then follow $n$ lines of each test case, each with two integers $d_i$ and $a_i$ ($1\le d_i$, $a_i\le 10^6$), the day on which the milk was acquired and the number of pints acquired. They are sorted in increasing values of $d_i$, and all values of $d_i$ are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输出格式

For each test case, output a single integer, the number of milk satisfaction days.

样例 #1

样例输入 #1

6
1 1 3
1 5
2 3 3
1 5
2 7
4 5 2
1 9
2 6
4 9
5 6
5 2 4
4 7
5 3
7 1
11 2
12 1
4 1 3
5 10
9 4
14 8
15 3
5 5 5
8 9
10 7
16 10
21 5
28 9

样例输出 #1

3
3
4
5
10
6

解题思路

这题要求优先喝新鲜的牛奶，也就是先进先出，我们可以使用一个栈来维护这个过程。

首先，枚举天数显然是容易超时的，因为枚举天数的话，对于没喝完的牛奶还会再次入栈，这样时间复杂度明显过大了。

那么，我们应该枚举购买记录才对，维护两次购买牛奶之间的天数之间的牛奶信息，存入栈内，这样整体的时间复杂度最多就是$O(n)$了。

一个细节就是，我们可以最后在栈内插入一个$inf$的天数，价值为$0$的哨兵，这样就不用特判最后一个购买记录了。

代码

const int N = 1e5 + 10;

void solve() {
	int n, m, k;
	std::cin >> n >> m >> k;

	std::vector<pii>a(n + 2);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i].first >> a[i].second;
	}
	a[n + 1] = { inf, 0LL };
	

	int lstd = 0 , res = 0;

	std::stack<pii>S;
	for (int i = 1;i<=n+1;++i) {
		auto [d, v] = a[i];

		int now = m;
		while (lstd < d && S.size()) {
			auto [pd, pv] = S.top(); S.pop();
			
			if (pd + k <= lstd) continue; //过期了

			if (pv >= now) {
				int s = std::min({ d - lstd, pd + k - lstd, (pv - now) / m  + 1}); 
				
				res += s; lstd += s;
				pv -= now + (s - 1) * m;
				now = m;

				if (pv) S.push({ pd,pv });
			}
			else {
				now -= pv;
			}
		}

		S.push({ d,v });
		lstd = d;
	}

	std::cout << res << "\n";
}

signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int t = 1;
	std::cin >> t;

	while (t--) {
		solve();
	}
};