20260221：AtCoder Beginner Contest 446

百会（bestWit）| 百炼成钢，融会贯通，助力GESP备考

哈喽，备战GESP的同学们～百会（bestwit）AtCoder题解来啦！每周1次更新，聚焦竞赛高频题型，贴合GESP入门难度，帮大家拆解解题思路、掌握解题技巧，夯实编程基础，为GESP考试做好准备。

题目

题目编号：C ：Omelette Restaurant 题目难度：★★★☆☆（贴合GESP 4-5级难度）题目链接：C - Omelette Restaurant

本题为 AtCoder 经典的 300 点模拟类题目，核心考察鸡蛋库存的时间维度管理，既可以用直观的「队列模拟」（官方解法）还原业务流程，也可以用更简洁的「前缀和约束」思路（优化解法）快速求解，两种思路各有优势，适合不同解题习惯。本文重点详细解释后一种解法。

题目大意

餐厅营业 N 天，每日执行 “采购鸡蛋→使用鸡蛋→清理过期鸡蛋” 三个操作：

第 i 天早上采购 Aᵢ个鸡蛋；
中午按采购顺序使用 Bᵢ个鸡蛋（保证无短缺）；
晚上清理采购后超过 D 天的鸡蛋；要求计算 N 天结束后剩余的鸡蛋数量，需处理多组测试用例。

限制条件：

1≤T≤2×10 $^5$
1≤D≤N≤2×10 $^5$
1≤Ai,Bi≤10
第N天的鸡蛋肯定够用
N天的鸡蛋的总和<= 2×10 $^5$
所有输入都为整数

输入输出

输入为如下格式：

T
case1 
case2 
⋮
caseT

输出为如下格式：

T 行
第i 行 (1≤i≤T)输出为第i个测试Case的答案。

输入样例：

输出样例：

3
5
0

解题思路

本题的核心是将 “鸡蛋过期清理” 转化为采购量前缀和的阈值约束：

用a数组存储采购量前缀和，通过i+d天的累计使用量限制前n-d天的采购量上限（模拟过期清理）；
用b数组存储使用量前缀和，代表累计消耗的鸡蛋总数；
最终剩余鸡蛋数 = 受约束的累计采购量 - 累计使用量。

代码

C++

// 万能头文件，包含C++所有常用库
#include <bits/stdc++.h>

using namespace std;

// 全局变量（数据范围较大，使用全局数组避免栈溢出）
int c, t, n, d;           // t:测试用例数 n:数组长度 d:滑动窗口/限制参数
int a[200005], b[200005];  // a:题目给定的原始数组  b:前缀和限制数组

int main(){
    // 读入测试用例数量
    cin >> t;
    // 循环处理每个测试用例
    while (t--){
        // 读入当前用例的 n（数组长度）和 d（参数）
        cin >> n >> d;
        
        // 读入数组 a 的 n 个元素
        for (int i = 1;i <= n;i++)    
            cin >> a[i];
        
        // 读入数组 c，并计算数组 b 的前缀和
        // b[i] 表示前 i 个 c 的总和，作为上限限制
        for (int i = 1;i <= n;i++){
            cin >> c;
            b[i] = b[i - 1] + c;
        }
        
        // 核心处理：前 n-d 个位置，累加后不能超过 b[i+d] 的上限
        for (int i = 1;i <= n - d;i++){
            // a[i] 累加前一项的值，得到当前累计值
            a[i] += a[i - 1];
            // 如果累计值超过上限 b[i+d]，则强制封顶
            if (a[i] > b[i + d]){
                a[i] = b[i + d];
            }
        }        
        
        // 处理后半段：从 n-d+1 到 n，直接累加，无上限限制
        for (int i = n - d + 1;i <= n;i++){
            a[i] += a[i - 1];
        }
        
        // 输出最终答案：a 数组总和 - b 数组总和
        cout << a[n] - b[n] << "\n";
    }
}

总结

核心思想：将 “过期清理” 转化为采购量前缀和的阈值约束，用b[i+d]作为前 i 天采购量的上限；

分段处理：前 n-d 天受过期约束，后 d 天无约束，贴合鸡蛋过期的时间规则；

效率优化：时间复杂度 O (N)，空间复杂度 O (N)，完全满足题目 2 秒时间限制和 1024MiB 内存限制。

该解法通过前缀和与分段约束，极简地实现了鸡蛋库存的模拟，是本题的最优解法之一，代码简洁且完全贴合题意要求

最后，祝大家在后续的AtCoder比赛中，顺利AC每一道C题，稳步提升！后续我们会逐步更新难度更高的题解，贴合GESP进阶考点，陪大家一起“百炼成钢”。

下期预告：AtCoder Beginner Contest 447，经典的 300 点模拟类题目，提供最贴合小学生的解法。记得关注公众号，第一时间获取更新通知～

20260221：AtCoder Beginner Contest 446 ​

题目 ​

题目大意 ​

限制条件： ​

输入输出 ​

解题思路 ​

代码 ​

总结 ​

20260221：AtCoder Beginner Contest 446

题目

题目大意

限制条件：

输入输出

解题思路

代码

总结