推公式

推公式

1、耍杂技的牛

描述：

​ 有N头牛，每头牛都有自己的 重量W 和强壮程度 S，奶牛们站在彼此的身上，形成一个高高的垂直堆叠，一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

​ 您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

思路：

​ 按照wi + si从小到大排序，最大的危险系数一定是最小的。

代码模板：

for (int i = 0; i < n; i ++)
    {
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {s + w, w};
    }

sort(cow, cow + n);

int res = -2e9, sum = 0;

for (int i = 0; i < n; i ++)
{
    //取出当前牛的重量和强壮值
    int w = cow[i].second, s = cow[i].first - w;
    res = max(res, sum - s);    //更新最大的危险系数
    sum += w;   //更新后一头牛所需要承担的重量
}

printf("%d", res);