题目125. 耍杂技的牛题目描述农民约翰的 N 头奶牛编号为 1…N计划逃跑并加入马戏团为此它们决定练习表演杂技。奶牛们不是非常有创意只提出了一个杂技表演叠罗汉表演时奶牛们站在彼此的身上形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量不包括它自己减去它的身体强壮程度的值现在称该数值为风险值风险值越大这只牛撑不住的可能性越高。您的任务是确定奶牛的排序使得所有奶牛的风险值中的最大值尽可能的小。输入第一行输入整数 N表示奶牛数量。接下来 N 行每行输入两个整数表示牛的重量和强壮程度第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。输出输出一个整数表示最大风险值的最小可能值。数据范围1≤N≤50000,1≤Wi≤10,000,1≤Si≤1,000,000,000时空限制1s / 64MB输入样例3 10 3 2 5 3 3输出样例2思路与简单证明按照siwi从小到大排序最大的危险系数是最小的。证明(邻项交换法)假设最优解不是按照ws从小到大排序的那么一定存在一对相邻项i和i1满足w i s i w i 1 s i 1 w_is_iw_{i1}s_{i1}wisiwi1si1的。第i个位置上的牛第i1个位置上的牛交换前w 1 w 2 . . . w i − 1 − s i w_1w_2...w_{i-1}-s_iw1w2...wi−1−siw 1 w 2 . . . w i − s i 1 w_1w_2...w_i-s_{i1}w1w2...wi−si1交换后w 1 w 2 . . . w i − 1 − s i 1 w_1w_2...w_{i-1}-s_{i1}w1w2...wi−1−si1w 1 w 2 . . . w i − 1 w i 1 − s i w_1w_2...w_{i-1}w_{i1}-s_iw1w2...wi−1wi1−si进行化简先减去w 1 w 2 . . . w i − 1 w_1w_2...w_{i-1}w1w2...wi−1再加上s i s i 1 s_is_{i1}sisi1可以得到第i个位置上的牛第i1个位置上的牛交换前s i 1 s_{i1}si1w i s i w_is_iwisi交换后s i s_isiw i 1 s i 1 w_{i1}s_{i1}wi1si1由于w和s都是1的数所以w i s i s i w_is_is_iwisisi且w i s i w i 1 s i 1 w_is_iw_{i1}s_{i1}wisiwi1si1所以交换后的最大危险系数会变小或不变。代码#includebits/stdc.husingnamespacestd;constintN5000010;typedefpairint,intPII;intn,w,s,ans,sum,maxx-2e9;PII a[N];intmain(){cinn;for(inti0;in;i){cinws;a[i]{ws,s};}sort(a,an);for(inti0;in;i){anssum-a[i].second;maxxmax(maxx,ans);suma[i].first-a[i].second;}coutmaxx;return0;}结果
)
