解题思路

这道题目要求我们为N头奶牛找到一个叠罗汉的顺序，使得所有奶牛中承受的最大风险值最小化。每头奶牛的风险值定义为：它上方所有奶牛的重量之和减去它自身的力量值。我们需要确定一个最优的排列顺序，使得这个最大风险值尽可能小。

1. 问题分析

• 输入：N头奶牛，每头奶牛有重量W_i和力量S_i。
• 输出：在所有可能的排列中，使得最大风险值最小的那个值。

2. 关键观察

通过分析，我们发现最优的排列顺序应该按照奶牛的（重量 + 力量）之和进行升序排序。这是因为：

• 将（W_i + S_i）较小的奶牛放在上方，可以减少下方奶牛承受的总重量，从而降低整体风险。
• 这种排序方式能够平衡重量和力量的影响，确保最大风险值最小化。

3. 算法选择

• 排序：首先将所有奶牛按照（W_i + S_i）升序排序。
• 计算风险值：遍历排序后的奶牛，维护一个累加的重量和，计算每头奶牛的风险值（上方总重量 - 当前奶牛的力量），并记录最大值。

4. 具体步骤

1. 输入处理：读取奶牛的数量N，以及每头奶牛的重量和力量。
2. 排序：使用自定义的比较函数，按照（W_i + S_i）升序排序奶牛数组。
3. 计算最大风险值：
   • 初始化累加重量和为0。
   • 遍历奶牛数组，对于每头奶牛，计算其风险值（当前累加重量和 - 当前奶牛的力量），并更新最大风险值。
   • 将当前奶牛的重量加到累加重量和中。
4. 输出结果：打印计算得到的最大风险值。

5. 时间复杂度

• 排序：O(N log N)，使用快速排序或归并排序。
• 遍历计算：O(N)，线性遍历排序后的数组。
• 总复杂度：O(N log N)，适用于大规模数据（N ≤ 50,000）。

解决代码

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

const int N = 50000;

struct Cow {
    int weight;
    int strength;
};

bool compare(const Cow &a, const Cow &b) {
    return (a.weight + a.strength) < (b.weight + b.strength);
}

Cow cows[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &cows[i].weight, &cows[i].strength);
    }

    sort(cows, cows + n, compare);

    int total_weight = 0;
    int max_risk = -cows[0].strength; // 初始化为第一头奶牛的风险（上方无奶牛，总重量为0）

    for (int i = 0; i < n - 1; ++i) {
        total_weight += cows[i].weight;
        int current_risk = total_weight - cows[i + 1].strength;
        if (current_risk > max_risk) {
            max_risk = current_risk;
        }
    }

    printf("%d\n", max_risk);

    return 0;
}

代码解释

1. 结构体定义：Cow结构体存储奶牛的重量和力量。
2. 比较函数：compare函数定义排序规则，按照（重量 + 力量）升序排列。
3. 输入处理：读取奶牛数量n和每头奶牛的属性。
4. 排序：使用sort函数和自定义比较规则对奶牛数组进行排序。
5. 计算最大风险值：
   • 初始化total_weight为0，max_risk为第一头奶牛的风险（上方无奶牛）。
   • 遍历奶牛数组，更新累加重量和，计算每头奶牛的风险值，并维护最大风险值。
6. 输出结果：打印最大风险值。

这种方法确保了在最优时间复杂度内解决问题，适用于题目给定的数据规模。