J. The Parade - 题解

比赛与标签

比赛: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) 标签: binary search, greedy 难度: *1800

题目大意喵~

主人，你好呀~！这道题目是关于阅兵方阵的喵！(ฅ'ω'ฅ)

我们要为柏林联合军准备一场盛大的阅兵式。士兵们会被分成 k 个方阵（行），并且每个方阵的人数必须完全相同。

阅兵的编队有两个非常重要的规则哦：

1. 所有 k 个方阵，每行的人数都要一样多。
2. 在同一个方阵里，所有士兵的身高差不能超过 1。也就是说，一个方阵里只能有身高为 i 的士兵，或者身高为 i 和 i+1 的士兵混合。

我们会得到每种身高（从 1 到 n）的士兵各有多少人。我们的任务，就是从所有士兵中挑选出一部分，组成符合上述规则的方阵，并让参加阅兵的总人数最多！我们要输出这个最大的人数，喵~

简单来说，就是求在满足“同排身高差不超过1”和“每排人数相等”的条件下，k 排总共最多能有多少士兵参加阅兵。

解题思路呐~

看到“最大化总人数”这种字眼，聪明的猫娘我呀，第一反应就是——这可能可以用二分答案来解决哦！(>^ω^<)

我们的最终答案是 k * x，其中 x 是每个方阵的人数。因为 k 是固定的，所以最大化总人数就等价于最大化每个方阵的人数 x。

那为什么可以二分呢？主人请想一下，如果我们能成功安排 k 个方阵，每个方阵有 x 个人，那么我们肯定也能安排出每个方阵 x-1 个人的情况（只需要从每个排好的方阵里去掉一个人就行了嘛）。这种“如果x可以，那么比x小的数也一定可以”的性质，就是单调性！这正是二分答案大显身手的地方。

所以，我们的整体思路就是：

1. 二分查找 每个方阵可能的最大人数 x。
2. 对于每一个猜想的 x，我们写一个 check(x) 函数来判断：我们手头的士兵，够不够组成 k 个每方阵 x 人的队伍呢？
   • 如果 check(x) 返回 true，说明 x 个人是可行的，我们或许可以试试更多的人，所以我们让搜索区间的下界变大 low = mid。
   • 如果 check(x) 返回 false，说明 x 个人太多啦，安排不过来，我们只能试试少一点的人，所以让搜索区ions上界变小 high = mid - 1。

check(x) 的贪心策略

check(x) 函数是整个解法的核心！我们要怎么判断 x 个人一排是否可行呢？这里就要用到贪心的思想啦。

因为一个方阵里只能有身高相邻的士兵（比如身高 i 和 i+1），所以我们最好按身高从小到大的顺序来处理士兵，这样最有效率！

我们从身高为 1 的士兵开始，依次向后处理到身高为 n 的士兵。

假设我们正在处理身高为 i 的士兵。我们不仅有 c[i] 个身高为 i 的士兵，可能还有一些处理身高 i-1 时剩下的士兵。我们把这些剩下的士兵称为 carry。这些 carry 士兵的身高都是 i-1，正好可以和身高为 i 的士兵组队！

所以，在第 i 步，我们总共有 carry + c[i] 个士兵可以用来组队。我们可以组成 (carry + c[i]) / x 个完整的方阵。我们把这些新组成的方阵数量累加起来。

组完队后，还剩下 (carry + c[i]) % x 个士兵。这些士兵可以留给下一步，和身高为 i+1 的士兵组队吗？

这里有一个关键点哦！要和身高为 i+1 的士兵组队，这些剩下的士兵身高必须是 i 才行。那些身高为 i-1 的 carry 士兵是不能和 i+1 的士兵组队的！

那么，我们能留给下一步的“新 carry”应该是多少呢？

1. 它不能超过剩下的总人数，也就是 (carry + c[i]) % x。
2. 它也不能超过我们本来拥有的身高为 i 的士兵数量 c[i]。因为剩下的士兵里，最多只有 c[i] 个是身高为 i 的。

所以，能留给下一步的 carry 就是 min((carry + c[i]) % x, c[i])。这一个贪心选择，保证了我们总是最大化地利用当前身高的士兵去和下一个身高的士兵配合，喵~

我们一路从身高 1 贪心到 n，只要在任何一步，累计组成的方阵数量达到了 k，check(x) 就成功返回 true！如果遍历完所有身高都凑不够 k 个方阵，那就返回 false。

二分查找结束后，我们得到的 low 就是每个方阵能容纳的最大人数 x，最终答案就是 low * k 啦！

代码实现喵！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

// check(x) 函数：判断每个方阵 x 个人是否可行
bool check(ll x, const vector<ll>& c, ll k) {
    // 如果每个方阵 0 个人，那当然是可行的啦~
    if (x == 0) {
        return true;
    }

    ll rows = 0;    // 已经成功组成的方阵（行）数
    ll carry = 0;   // 从上一个身高留下来，可以和当前身高士兵组队的士兵数
    int n = c.size();

    // 从身高最小的开始，贪心地处理每一种身高的士兵
    for (int i = 0; i < n; i++) {
        // 当前可用的士兵 = 上一轮剩下的(身高i-1) + 当前身高的(身高i)
        ll available = carry + c[i];
        
        // 用这些士兵能组成多少个完整的方阵
        rows += available / x;
        
        // 如果组成的方阵数已经够 k 个了，说明 x 是可行的，直接返回 true
        if (rows >= k) {
            return true;
        }

        // 剩下的士兵，准备留给下一个身高(i+1)使用
        carry = available % x;
        // 关键的贪心步骤！
        // 留给下一轮的士兵身高必须是 i，所以数量不能超过 c[i]
        // 同时也不能超过总的剩余数量 available % x
        carry = min(carry, c[i]);
    }
    
    // 遍历完所有身高，都没能凑齐 k 个方阵，说明 x 太大了
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> c(n);
        ll total = 0;
        for (int i = 0; i < n; i++) {
            cin >> c[i];
            total += c[i];
        }

        // 二分查找的范围
        ll low = 0; // 每排最少 0 个人
        // 每排最多的人数，不会超过总人数 / k
        ll high = total / k; 

        // 二分查找最大的可行 x (low)
        while (low < high) {
            // 向上取整，避免死循环，并且帮助我们逼近上界
            ll mid = (low + high + 1) / 2;
            if (check(mid, c, k)) {
                // mid 可行，说明答案可能就是 mid 或者更大
                low = mid;
            } else {
                // mid 不可行，说明答案一定比 mid 小
                high = mid - 1;
            }
        }
        
        // 最终的 low 就是每个方阵的最大人数 x，总人数就是 low * k
        cout << low * k << '\n';
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N * log(S/K)) 的说。 这里的 N 是身高的种类数，S 是士兵总数。二分答案的搜索范围是从 0 到 S/K，所以二分部分的时间是 log(S/K)。每次二分我们都需要调用 check 函数，而 check 函数需要遍历一遍所有身高，复杂度是 O(N)。所以总时间复杂度就是 O(N * log(S/K)) 呐。

• 空间复杂度: O(N) 的说。 我们主要用了一个 vector 来存储 N 种身高的士兵数量，所以空间复杂度是 O(N)。

知识点与总结喵~

这道题真是一道非常经典的 “二分答案 + 贪心” 结合的题目呢！通过这道题，主人可以复习和掌握以下知识点：

1. 二分答案的应用场景: 当题目要求解一个最大值（或最小值），并且这个解满足单调性时，就可以考虑二分答案。把一个求解问题，转化为一个判定问题。
2. 贪心算法的设计: check 函数中的贪心是解题的关键。如何做出当前最优的局部决策（即 carry = min(leftover, c[i])），从而导向全局最优解，是贪心问题的魅力所在。
3. 大数处理: 题目中的 k 和 c_i 都可以非常大，所以一定要记得使用 long long 来避免溢出哦，这是竞赛中的好习惯！
4. 二分写法的细节: mid = (low + high + 1) / 2 这种写法是用于查找满足条件的“最大值”的，与 high = mid - 1 配对使用，可以有效避免死循环，帮助我们找到区间的右边界。

希望这篇题解能帮助到主人哦！继续加油，算法的世界还有很多有趣的冒险在等着我们呢，喵~ (ฅ'ω'ฅ)