耍杂技的母牛（母牛叠罗汉问题）

问题：

农民约翰的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;
	
}
/*
输入：
   3
   10 3
   2 5
   3 3
输出：
  2
 */ 

最后

以上就是俭朴画笔为你收集整理的耍杂技的母牛（母牛叠罗汉问题）的全部内容，希望文章能够帮你解决耍杂技的母牛（母牛叠罗汉问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。