相邻的糖果

[编程题]相邻的糖果

热度指数：1761 时间限制：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;
}

发表于 2026-02-07 00:58:02 回复(4)

C++

Vsg21

其实有道 $m=2$ 的原题，答案是从左到右贪心吃相邻中右边的糖果，这道题类比就是，用滑动窗口优先吃右边的糖果，保持所有窗口的 $sum \leq x$ 。
初始化第一个窗口就是从右吃到左，直到第一个窗口右 $sum\leq x$ 。
关于维护，由于在上一窗口 $sum \leq x$ ，所以在这一窗口中 $sum - a_i \leq x$ ，因此我们在维护窗口转移时最多只需要对窗口最右侧的那一袋子进行操作。

时间复杂度 $O(n)$ 。

#include <iostream>
#include <vector>
using namespace std;
#define int long long

int n,m,x,ans;
vector<int>a;
signed main() {
    cin>>n>>m>>x;
    ans = 0;
    a=vector<int>(n+1, 0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    if(m>=n){
        for(int i=1;i<=n;i++){
            ans += a[i];
        }
        cout<<ans-x<<"\n";
    }

    int sum = 0;
    for(int i=1;i<=n;i++){
        if(i > m)sum -= a[i-m];
        if(sum + a[i] > x){
            int d = sum + a[i] - x;
            a[i] -= d;
            ans += d;
        }
        sum += a[i];
    }

    cout<<ans<<"\n";
}

发表于 2026-02-07 10:45:46 回复(0)