B. Addition on a Segment

时间限制：每测试点2秒
内存限制：每测试点512MB

问题描述

你从一个整数数组 $a$ 开始，初始时包含 $n$ 个零。你需要恰好执行 $n$ 次以下操作：

• 选择两个整数 $l$ 和 $r$ ($1 \leq l \leq r \leq n$)，并将每个满足 $l \leq i \leq r$ 的 $a_i$ 增加 $1$。

给定一个包含 $n$ 个整数的数组 $b$。你的任务是为每个操作选择 $l$ 和 $r$，使得：

• 所有 $n$ 次操作执行完毕后，可以通过重新排列元素使 $a$ 等于 $b$；
• 所有操作中 $r-l+1$（区间长度）的最大值尽可能大。

问 $r-l+1$ 的最大可能值是多少？

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 $t$ ($1 \leq t \leq 10^4$)。接下来是测试用例描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) —— 数组 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $b_i$ ($0 \leq b_i \leq n$) —— 数组 $b$ 的元素。

输入的其他约束条件： - 至少存在一种方法为每个操作选择 $l$ 和 $r$，并在最后重新排列元素使 $a$ 等于 $b$； - 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 问题的答案。

样例输入

3
5
0 5 1 0 1
3
3 2 1
5
1 1 1 1 1

样例输出

3
3
1

样例说明

考虑第一个测试用例。如果 $n$ 次操作如下： - $l=3, r=3$ - $l=1, r=3$
- $l=3, r=3$ - $l=3, r=3$ - $l=3, r=3$

数组 $a = [1,1,5,0,0]$，可以通过重新排列元素使其等于 $[0,5,1,0,1]$。在这种情况下，$r-l+1$ 的最大值是 $3$。可以证明这是最优答案。

在第二个测试用例中： - $l=1, r=3$ - $l=2, r=3$ - $l=3, r=3$

答案是 $3$。

我的AC 代码

// Problem: CF 2170 B
// Contest: Codeforces - Educational Codeforces Round 185 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2170/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;

int check(int x,int sum){
    if(sum-x>=n-1) return 1;
    else return 0;
}

void solve(){
    cin>>n;
    vector<int> a(n);
    int sum=0,cnt=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        if(a[i]) cnt++;
    }

    int l=0,r=cnt;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid,sum)) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
    return ;
}


signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

题目整理：CF 2170 B - Addition on a Segment

1. 你的代码思路分析 (Binary Search on Answer)

你的解法非常巧妙，跳过了复杂的构造过程，直接通过二分答案来锁定结果。

核心逻辑

1. 数据特征提取：

   • sum：数组 $b$ 的总和。因为每次操作是区间加 1，所以 $n$ 次操作的总长度之和必须等于 sum。

   • cnt：数组 $b$ 中非零元素的个数。这决定了我们一次操作最多能覆盖多长的区间（因为操作产生的非零数不能超过最终所需的非零数位置）。

2. 二分答案：

   • 你二分的 mid 代表我们想要尝试的最大区间长度。

   • 下界 l = 0。

   • 上界 r = cnt：这是一个非常关键的观察。一次操作的长度不可能超过非零元素的总数，否则就会产生多余的非零数，导致无法重排成 $b$。

3. Check 函数 (贪心判断)：

   • if(sum - x >= n - 1)

   • 这行代码的含义是：如果我们消耗了 x 的长度作为“最大操作”，那么剩下的 sum - x 必须足够分给剩下的 n - 1 次操作。

   • 因为题目要求 $1 \le l \le r \le n$，所以每次操作长度至少为 1。

   • 只要剩余的总和 $\ge$ 剩余的操作次数 $\times 1$，这个方案就是可行的。

复杂度分析

• 时间复杂度：$O(N + \log N)$。遍历数组求和 $O(N)$，二分 $O(\log N)$。这在 $N=2 \cdot 10^5$ 下运行极快。

• 空间复杂度：$O(N)$，用于存储数组。

---

2. 进阶分析：从二分到 O(1) 数学解

你的二分法是完全正确的，但如果我们仔细分析你的 check 函数和上界，会发现这其实是一个可以直接计算的数学问题。

推导

我们需要满足两个硬性限制：

1. 限制一（非零数限制）：

   最大操作长度不能超过非零元素的个数。

   $$Ans \le cnt$$

   (理由：如果一次操作长度为 $L$，那么至少有 $L$ 个位置变成了非零。如果 $L > cnt$，则非零数过多，无法匹配 $b$。)

2. 限制二（总和限制 / 贪心）：

   我们要最大化某一次操作的长度 $L_{max}$。

   这就意味着我们要最小化其余 $n-1$ 次操作的长度。

   已知每次操作长度至少为 1。

   $$TotalSum = L_{max} + \sum_{i=1}^{n-1} L_i$$

   为了让 $L_{max}$ 最大，让其余 $L_i$ 取最小值 $1$：

   $$sum = L_{max} + (n-1) \times 1$$
   $$L_{max} = sum - (n - 1)$$

   所以：

   $$Ans \le sum - n + 1$$

最终公式

结合以上两个限制，答案就是它们中的较小值：

$$Ans = \min(cnt, \ sum - n + 1)$$

优化后的代码示例

不需要二分，也不需要 check 函数：

C++

void solve(){
    cin >> n;
    long long sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        sum += x;
        if(x > 0) cnt++;
    }
    // 直接输出最小值
    cout << min((long long)cnt, sum - n + 1) << "\n";
}

这个 $O(1)$ 的思路其实就隐藏在你的二分逻辑里（r=cnt 对应限制一，check 对应限制二）。

---

3. 知识点总结 (Review)

这道题非常适合用来训练逆向思维和贪心策略。

📌 技巧：最大化单个值的贪心策略

当题目问“最大化其中一个变量 $X$”且满足总量 $S$ 固定时（$X + Y + Z + \dots = S$）：

• 策略是：让其他所有变量取理论最小值。

• 在本题中，其他 $n-1$ 次操作的理论最小长度是 $1$。

📌 技巧：重排 (Permutation) 的暗示

题目中出现“可以通过重新排列使 $a$ 等于 $b$”，通常意味着：

• 位置不重要：我们不需要关心具体是在 $[1, 3]$ 加还是 $[2, 4]$ 加。

• 数值统计重要：我们只关心值的总和 (sum) 和 非零值的个数 (cnt)。

• 不要尝试构造：很多时候不需要构造出具体的 $l, r$，只需要判断数值关系是否满足约束。

📌 思维误区提醒

• 刚看到题目可能会想：“我怎么知道哪次操作对应 $b$ 里的哪个数字？”

• 这是陷阱。题目只问长度，且允许重排，说明具体的对应关系不需要我们去维护，只需要维护宏观的“总量”和“个数”限制即可。

下一步建议

如果整理到 Obsidian，建议标签：#Greedy #Math #Constructive Algorithms。

可以将这道题作为 "Sum Constraint Maximization" (定和最大化) 的典型案例。