CodeRush Round 1 (Div. 4) 官方题解

Problem A. 瓜分金币

题目大意

桌上有 $n$ 枚硬币，第 $i$ 枚硬币的面值为 $a_i$。想从中拿走若干枚硬币，使得拿走的硬币总面值严格大于剩余硬币的总面值，且拿走的硬币数量尽可能少。输出最少需要拿走多少枚硬币。

题解

这是一道贪心题。

要让拿走的硬币面值严格大于剩余面值，等价于拿走的面值 $> \frac{\text{总和}}{2}$。

贪心策略：每次拿走当前面值最大的硬币。这样可以用最少的硬币达到目标。

证明：设硬币面值总和为 $S$，我们需要拿走面值 $> S/2$。如果我们拿走面值最大的硬币，每一步都能让累计面值增长最快，因此能最快达到目标。

算法步骤：

1. 计算所有硬币面值总和 $sum$
2. 将硬币按面值从大到小排序
3. 从大到小依次取硬币，累计面值直到超过 $sum/2$
4. 输出取走的硬币数量

时间复杂度：$O(n \log n)$（排序）

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[105];  // 硬币面值数组

int main() {
    int n;
    cin >> n;
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];  // 计算总面值
    }
    
    // 从大到小排序
    sort(a, a + n, greater<int>());
    
    int cnt = 0;       // 拿走的硬币数量
    int my_sum = 0;    // 拿走的面值总和
    
    for (int i = 0; i < n; i++) {
        my_sum += a[i];
        cnt++;
        // 拿走的面值严格大于剩余面值
        // 等价于 my_sum > sum - my_sum
        if (my_sum > sum - my_sum) {
            break;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

---

Problem B. 01子矩阵最大贡献

题目大意

给定一个 $n \times m$ 的 01 矩阵，定义任意子矩阵的"贡献"为 $|c_0 - c_1|$（$c_0$ 是 0 的个数，$c_1$ 是 1 的个数）。求所有连续子矩阵中贡献的最大值。

数据范围：$1 \le n, m \le 12$

题解

由于 $n, m \le 12$，矩阵最多 $12 \times 12 = 144$ 个元素。数据范围很小，可以直接暴力枚举所有子矩阵。

算法步骤：

1. 枚举子矩阵的左上角 $(i1, j1)$ 和右下角 $(i2, j2)$
2. 统计该子矩阵中 0 和 1 的个数
3. 计算贡献 $|c_0 - c_1|$ 并更新最大值

时间复杂度：$O(n^2 m^2 \cdot nm) = O(n^3 m^3)$，对于 $n=m=12$ 约为 $10^6$ 级别，完全可以通过。

参考代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string grid[15];  // 矩阵，每行一个字符串

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    int max_contrib = 0;
    
    // 枚举子矩阵左上角
    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = 0; j1 < m; j1++) {
            // 枚举子矩阵右下角
            for (int i2 = i1; i2 < n; i2++) {
                for (int j2 = j1; j2 < m; j2++) {
                    int c0 = 0, c1 = 0;
                    // 统计子矩阵中 0 和 1 的个数
                    for (int i = i1; i <= i2; i++) {
                        for (int j = j1; j <= j2; j++) {
                            if (grid[i][j] == '0') c0++;
                            else c1++;
                        }
                    }
                    // 计算贡献并更新最大值
                    int contrib = abs(c0 - c1);
                    if (contrib > max_contrib) {
                        max_contrib = contrib;
                    }
                }
            }
        }
    }
    
    cout << max_contrib << endl;
    return 0;
}

---

Problem C. 巧克力对吃

题目大意

$n$ 块巧克力排成一排，第 $i$ 块吃完需要 $t_i$ 秒。Aki 从左往右吃，Bob 从右往左吃。如果两人同时开始吃同一块，Bob 让给 Aki。输出两人各吃了多少块。

题解

这是一道模拟题，可以用双指针来模拟两人吃巧克力的过程。

关键思路：

• 用指针 $l$ 表示 Aki 当前要吃的巧克力（从左端开始）
• 用指针 $r$ 表示 Bob 当前要吃的巧克力（从右端开始）
• 记录两人已经花费的时间，时间少的人先"吃"下一块

算法步骤：

1. 初始化 Aki 的时间 t1 = 0，Bob 的时间 t2 = 0
2. 当 $l \le r$ 时循环：
   • 如果 t1 <= t2，Aki 吃第 $l$ 块，t1 += t[l]，l++
   • 否则，Bob 吃第 $r$ 块，t2 += t[r]，r--
3. 如果两人时间相等且 $l = r$（同时到达同一块），根据 t1 <= t2 的判断，这块归 Aki

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

参考代码

#include <iostream>
using namespace std;

int t[100005];  // 每块巧克力所需时间

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    
    int l = 0, r = n - 1;   // 双指针
    int t1 = 0, t2 = 0;     // 两人累计时间
    int a1 = 0, a2 = 0;     // 两人吃的巧克力数量
    
    while (l <= r) {
        if (t1 <= t2) {
            // Aki 的时间少（或相等），Aki 吃
            t1 += t[l];
            l++;
            a1++;
        } else {
            // Bob 的时间少，Bob 吃
            t2 += t[r];
            r--;
            a2++;
        }
    }
    
    cout << a1 << " " << a2 << endl;
    return 0;
}

---

Problem D. Aki的优等生

题目大意

有 $n$ 名同学，每人有姓名 $s_i$、算法分 $a_i$、数学分 $b_i$、英语分 $c_i$。定义总分 $t_i = a_i + b_i + c_i$。按以下多关键字排序：

1. 总分从大到小
2. 算法分从大到小
3. 数学分从大到小
4. 姓名字典序从小到大

输出排序后的结果。

题解

这是一道结构体排序题。使用自定义比较函数来实现多关键字排序。

注意事项：

• 姓名按字典序升序
• 其他分数按降序

时间复杂度：$O(n \log n)$

参考代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int a, b, c;   // 算法分、数学分、英语分
    int total;      // 总分
} stu[200005];

// 自定义比较函数：多关键字排序
bool cmp(const Student &x, const Student &y) {
    if (x.total != y.total) return x.total > y.total;     // 总分降序
    if (x.a != y.a) return x.a > y.a;                      // 算法分降序
    if (x.b != y.b) return x.b > y.b;                      // 数学分降序
    return x.name < y.name;                                 // 姓名升序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].a >> stu[i].b >> stu[i].c;
        stu[i].total = stu[i].a + stu[i].b + stu[i].c;  // 计算总分
    }
    
    // 排序
    sort(stu, stu + n, cmp);
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << stu[i].name << " " << stu[i].total << " ";
        cout << stu[i].a << " " << stu[i].b << " " << stu[i].c << "\n";
    }
    
    return 0;
}

---

Problem E. 读书计划

题目大意

有 $n$ 本书排成一排，第 $i$ 本需要 $a_i$ 分钟读完。有 $t$ 分钟空闲时间。选择一个起点 $l$，按顺序读 $l, l+1, l+2, \dots$，每本书必须读完。输出最多能读完多少本书。

题解

这是一个典型的滑动窗口问题。

对于每个起点，我们需要找到最远的终点使得区间和不超过 $t$。使用滑动窗口可以高效解决。

算法步骤：

1. 使用双指针维护一个窗口
2. 右指针向右扩展，累加窗口内的和
3. 当窗口和超过 $t$ 时，左指针向右收缩
4. 每次更新窗口内的最大长度

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

参考代码

#include <iostream>
using namespace std;

long long a[100005];  // 每本书所需时间

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long t;
    cin >> n >> t;
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int max_books = 0;
    int l = 0;           // 左指针
    long long sum = 0;    // 窗口内的时间和
    
    // 滑动窗口
    for (int r = 0; r < n; r++) {
        sum += a[r];  // 扩展右边界
        
        // 当窗口和超过 t 时，收缩左边界
        while (sum > t) {
            sum -= a[l];
            l++;
        }
        
        // 更新最大长度
        if (r - l + 1 > max_books) {
            max_books = r - l + 1;
        }
    }
    
    cout << max_books << endl;
    return 0;
}

---

Problem F. 开心农场2

题目大意

$N$ 个酒店形成环状，第 $i$ 个酒店每天消耗 $w_i$ 单位蔬菜，到下一个酒店的距离为 $d_i$。选择一个酒店旁建农场，农场所在酒店无需运输。货车从农场出发，依次运送蔬菜，运费 = 运输总重量 × 距离。求最小总运费。

题解

这是一道环形问题。如果暴力枚举每个农场位置并计算运费，时间复杂度为 $O(N^2)$，对于 $N \le 10^5$ 会超时。

我们需要利用递推公式来优化。

关键观察：

设 $f(k)$ 表示农场设在第 $k$ 号酒店时的总运费。

先计算 $f(0)$：农场设在 0 号酒店。

• 货车从 0 号酒店出发，依次给 1, 2, ..., N-1 号酒店送菜
• 初始剩余重量 = $\sum_{i=1}^{N-1} w_i = total\_W - w_0$
• 每经过一段路，运费 = 剩余重量 × 路段距离

递推公式：

考虑从农场位置 $k$ 移动到 $k+1$ 时，运费如何变化。

• 原来需要给 $k$ 号酒店送菜，现在不需要了（农场就在这）
• 原来不需要给 $k+1, k+2, \dots$ 送的菜（因为农场在 $k$ 时，这些路段的重量包含了 $w_k$），现在需要了

推导得到：

$$f(k+1) = f(k) + w_k \times total\_D - total\_W \times d_k$$

其中：

• $total\_W = \sum_{i=0}^{N-1} w_i$（总蔬菜量）
• $total\_D = \sum_{i=0}^{N-1} d_i$（总距离）

算法步骤：

1. 计算总蔬菜量 $total\_W$ 和总距离 $total\_D$
2. 计算初始运费 $f(0)$
3. 利用递推公式依次计算 $f(1), f(2), \dots, f(N-1)$
4. 取最小值

时间复杂度：$O(N)$

参考代码

#include <iostream>
using namespace std;

long long w[100005];  // 各酒店蔬菜消耗量
long long d[100005];  // 各路段距离（酒店 i 到 i+1）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    long long total_W = 0;  // 所有酒店蔬菜总重量
    long long total_D = 0;  // 所有路段总距离
    
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> d[i];
        total_W += w[i];
        total_D += d[i];
    }
    
    // 计算初始运费 f(0)：农场设在 0 号酒店时的总运费
    long long f0 = 0;
    long long rest = total_W - w[0];  // 初始剩余重量（无需给 0 号送）
    
    for (int i = 0; i < n - 1; i++) {
        // 遍历 0→1 到 (n-2)→(n-1) 的 n-1 段路
        f0 += rest * d[i];
        rest -= w[i + 1];  // 送完 i+1 号酒店，剩余重量减少
    }
    
    // 递推计算所有农场位置的运费，记录最小值
    long long min_cost = f0;
    long long current_f = f0;
    
    for (int i = 0; i < n; i++) {
        // 递推公式：f(i+1) = f(i) + w[i] * total_D - total_W * d[i]
        long long next_f = current_f + w[i] * total_D - total_W * d[i];
        if (next_f < min_cost) {
            min_cost = next_f;
        }
        current_f = next_f;
    }
    
    cout << min_cost << endl;
    return 0;
}