关于耍杂技的牛一题的思路+代码

50 阅读 0 评论 33 点赞

我是靠谱客的博主慈祥宝贝，最近开发中收集的这篇文章主要介绍关于耍杂技的牛一题的思路+代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来源：AcWing 125. 耍杂技的牛&洛谷 P1842 [USACO05NOV] 奶牛玩杂技

题目描述

农民约翰的N头奶牛（编号为1…N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量 W_i 以及自己的强壮程度 S_i。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入描述

第一行输入整数N，表示奶牛数量。
接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第 i 行表示第 i 头牛的重量 W_i 以及它的强壮程度 S_i。

输出描述

输出一个整数，表示最大风险值的最小可能值。

数据范围

1≤ N ≤50000,
1≤ W_i ≤10,000,
1≤ S_i ≤1,000,000,000

输入样例

3
10 3
2 5
3 3

输出样例

2

OP

这道题代码不难，主要是思路。

思路

我们可以把排序问题拆分成从输入顺序开始的足够多次对换，只要我们找到能更趋近与所求结果的对换条件，我们便可以依照此条件直接排序。

假设现在有两头牛，i 与 i + 1，我们要找到一种使对换后两牛最大危险值小于对换前的两牛最大危险值的条件。

由题意，对换前两牛（ i , i + 1 ）危险值分别为
$Q_i=W_1+W_2+...+W_{i-1} - S_i$
与
$Q_{i+1}=W_1+W_2+...+W_{i-1}+W_i - S_{i+1}$

对换后，（ i , i + 1 ）危险值分别为
$H_{i}=W_1+W_2+...+W_{i-1}+W_{i+1} - S_{i}$
与
$H_{i+1}=W_1+W_2+...+W_{i-1} - S_{i+1}$

省略掉相同部分，若要使 $MAX(W_{i+1} - S_{i} ,- S_{i+1} )≥MAX( - S_{i} ,W_i - S_{i+1})$
只需满足 $W_{i+1} - S_{i}≥W_i - S_{i+1}$
移项可得 $W_{i+1}+ S_{i+1}≥W_{i}+ S_{i}$

由此结论，我们可以直接按照 W_i+S_i 降序排列，即是最大风险值最小的情况，再遍历求出最大危险值。

代码

#include <bits/stdc++.h>
using namespace std;
struct co{int w,s;}cow[50004];
bool cmp(co a,co b)
{
    return a.w+a.s<b.w+b.s;
}
int main()
{
    int w,s,n,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&cow[i].w,&cow[i].s);
    }
    sort(cow+1,cow+n+1,cmp);
    int mi=0x87777777;//最小值
    long long wi=0;
    for(i=1;i<=n;i++)
    {
        mi=max((long long)mi,wi-cow[i].s);
        wi+=cow[i].w;
    }
    printf("%d",mi);
    return 0;
}