本文主要是介绍耍杂技的母牛（母牛叠罗汉问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：
农民约翰的N头奶牛（编号为1.. N ）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量wi 以及自己的强壮程度si
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
思路：
贪心算法的思想，将每个母牛的强壮程度和体重相加，再将其从小到大排序。这样能求出风险值最大的最小值。
设按照上述规则求得的答案为可行解c n t cntcnt 最优解为a n s ansans
运用反证法：
代码实现：
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N=100010;
int n;
typedef pair<int,int> PII;PII cows[N];int main()
{scanf("%d",&n);for(int i=0;i<n;i++){int w,s;scanf("%d%d",&w,&s);cows[i]={w+s,w}; }sort(cows,cows+n);int res=-2e9,sum=0;for(int i=0;i<n;i++){int w=cows[i].second; res=max(res,sum-cows[i].first+w);sum+=cows[i].second;}cout<<res;return 0;}
/*
输入：310 32 53 3
输出：2*/
这篇关于耍杂技的母牛（母牛叠罗汉问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
