相邻的糖果

[编程题]相邻的糖果

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个盒子摆成一排，每个盒子内都有a_i个糖果。
现在你可以执行以下操作：
·你可以选择任意一个盒子，在选择的盒子内吃掉一个糖果。
对你的要求如下：
·任何m个相邻的盒子内糖果数量不能超过x个。
请问，实现要求的最少操作次数是多少？

输入描述:

第一行三个数字n, m, x(2 ≤ n,m ≤ 10⁶,1 ≤ x ≤ 10⁹)。
第二行n个数字(1 ≤ a_i ≤ 10⁹)。

输出描述:

输出一个操作数，代表实现要求的最少操作数。

示例1

输入

3 2 3
2 1 2

输出

说明

2 1 2满足题目要求，任意相邻的两个数值之和均不超过3，所以不需要进行任何操作。

算法知识视频讲解

C++

Reisentyan

我们将使用拉马努金瞪眼法解决这一题

注意到，只用贪心就好了

从下标 1 开始累计糖果数量，就像滑动窗口那样维护

如果当前糖果数量太多，那就贪心的，吃最右边的糖果

易得，每个糖果袋子我们可以 O(1) 计算出要吃多少次。

当前糖果袋子吃完了，那我们就吃左边的糖果袋子，我们维护一个 nxt 数组，表示下一个要吃的糖果袋子在哪，可以使用递归：

	auto getnxt = [&](auto&&getnxt,int p)->int
		{
			if (nxt[p] == p - 1)return p;
			nxt[p] = getnxt(getnxt, nxt[p]);
			return nxt[p];
		};

似乎可以构造出最坏解，而且我不会证明复杂度，感性判断，每个袋子被访问的次数不会太多，就是这样！

注意到，代码要写成这样：

#include <cctype>
#include <cstdio>
#include <cstdint>
uint8_t buf[1 << 20], * p1, * p2;
#define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<20,stdin)),*p1++)
int readint() {
	int k = 0, f = 1, c = gc();
	for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
	for (; isdigit(c); c = gc()) k = k * 10 + (c ^ 48);
	return k * f;
}
ll cd[1001000];
int nxt[1001000];
void solve()
{
	int n = readint();
	int m = readint();
	ll x = readint();
	ll ans = 0;
	ll now = 0;
	auto getnxt = [&](auto&&getnxt,int p)->int
		{
			if (nxt[p] == p - 1)return p;
			nxt[p] = getnxt(getnxt, nxt[p]);
			return nxt[p];
		};
	ffp(i, 1, n)
	{
		cd[i] = readint();
		nxt[i] = i - 1;
		now += cd[i];
		now -= cd[max(i - m, 0)];
		int p = i;
		while(now > x)
		{
			ll sub = min((now - x), cd[p]);;
			ans += sub;
			now -=sub;
			cd[p] -= sub;
			p = getnxt(getnxt, p);
		}
	}
	cout << ans  << endl;
}

发表于今天 00:58:02 回复(2)