先说说，27届，知道自己算法不咋好，系统性刷题不久，但是头铁，二次挑战多多牛客笔试，战况：前两题我感觉是简单/中等贪心题，我没刷过，内容见图，通过88.89、28（加了个边界判断多了4%）

最后两题是困难级别的吧，我都没怎么看，记下来的就两道大家看图吧，内容和字迹比较潦草望各位见谅哈哈，祝秋招小伙伴们成功，我继续沉淀吧哈哈

作者：我是苍苍 链接：https://www.nowcoder.com/feed/main/detail/7db592f634b64856a158083c0363178f?sourceSSR=users 来源：牛客网

新编辑(和语言模型Kimi K3讨论了下，感觉这是合适的解决方法)：

第一题：数据中心巡检（灯状态反转）

你的思路（我理解的对吗？）

D[2][n]：D[0]存原始状态，D[1]存反转状态（即 1-a[i]）
cur = 0 表示"当前相当于被翻转了偶数次"
从左到右遍历：
  如果 D[cur][i] == 0（当前灯是灭的）
    次数++
    cur ^= 1（切换奇偶状态，因为按了按钮 i，i~n 全部翻转）

这个思路完全正确！ 你实际上是用 cur 的奇偶性代替了"当前位置被前面按过的按钮累计翻转了多少次"，这是一个 O(n) 的优雅做法。

为什么可能是 88.9%？

最可能的坑是 数组越界或下标问题： 循环写成 0 n 而不是 0 n-1：如果循环到 i=n，访问了未初始化内存，恰好那个值是 0，就会多算一次按钮。 数组开在栈上且不够大：如果写成 int D[2][100000]，而题目 n=100000，在 C++ 中栈空间可能爆掉（不同编译器栈大小不同），建议开全局或 vector。 输入格式：比如题目是 1-indexed 给出机柜编号，但你按 0-indexed 读入，导致错位。 标准写法（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int ans = 0;
    int flip = 0;  // 0: 偶数次翻转, 1: 奇数次翻转
    
    for (int i = 0; i < n; i++) {
        int actual = a[i] ^ flip;  // 当前灯的实际状态
        if (actual == 0) {
            ans++;
            flip ^= 1;  // 按按钮 i，i~n 翻转，后续所有灯奇偶性改变
        }
    }
    
    cout << ans << "\n";
    return 0;
}

你的双数组切换 cur ^= 1 和这个 flip ^= 1 本质一模一样，只是我省去了开二维数组的空间。如果这题卡你了，大概率是边界细节而非思路问题。

第二题：修整长跑赛道（最大化最小平整度）

你的思路

重复 m 次：
  枚举所有长度为 k 的连续区间，计算区间和
  选区间和最小的那个区间，给区间内每个 ai += 1
最后输出全局最小值

这个贪心策略是错误的。 "每次选和最小的区间" 并不能保证最终全局最小值最大。 反例（帮你找到丢分原因）

n=4, m=2, k=2
a = [1, 1, 100, 1]

按你的贪心： 第1次：区间 [0,1] 和=2，[1,2] 和=102，[2,3] 和=101 → 选 [0,1] → [2,2,100,1] 第2次：区间 [0,1] 和=4，[1,2] 和=102，[2,3] 和=101 → 选 [0,1] → [3,3,100,1] 最终最小值 = 1（第4条道完全没修到） 但最优解： 第1次：[0,1] → [2,2,100,1] 第2次：[2,3] → [2,2,101,2] 最终最小值 = 2

贪心只看了"当前哪块最穷"，但没看"哪块最需要被拉一把"。 这类让"最小值尽可能大"的问题，标准套路是二分答案。 正确思路：二分答案 + 差分验证 核心思想：假设我们想让最终每条道的平整度都 至少为 x，验证这个 x 是否能在 m 次操作内达成。

验证函数 check(x)： 从左到右遍历每条道。 用差分数组维护"当前位置已经被前面的操作加了多少"。 如果第 i 条道实际值 < x，说明必须从 i 开始往后修，需要修 (x - 实际值) 次。 每次操作覆盖 [i, i+k-1]，用差分在 i 处 +d，在 i+k 处 -d。 累加操作次数，如果超过 m 则 x 不可行。 二分范围：low = min(a)，high = min(a) + m（或更大，比如 2e9）。 标准写法（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    ll left = *min_element(a.begin(), a.end());
    ll right = left + m;  // 上界，每次操作最多让某个位置+1
    ll ans = left;
    
    auto check = [&](ll x) -> bool {
        vector<ll> diff(n + 1, 0);  // 差分数组，多开一位防止 i+k 越界
        ll cur = 0;      // 当前位置累计被加了多少
        ll used = 0;     // 已用操作次数

        for (int i = 0; i < n; i++) {
            cur += diff[i];
            ll actual = a[i] + cur;
            if (actual < x) {
                ll need = x - actual;  // 需要从 i 开始修 need 次
                if (need < 0) continue;
                used += need;
                if (used > m) return false;  // 操作次数超了
                cur += need;
                if (i + k < n) diff[i + k] -= need;  // 差分：影响范围到 i+k-1
            }
        }
        return true;
    };

    while (left <= right) {
        ll mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

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

复杂度 check() 是 O(n)，二分是 O(log(m))，总复杂度 O(n log m)，轻松通过。