農夫的N只牛(1<=n<=50,000)決定練習特技表演。 特技表演如下:站在對方的頭頂上，形成一個垂直的高度。 每頭牛都有重量(1 <= W_i <= 10,000)和力量(1 <= S_i <= 1,000,000,000)。奶牛崩潰的風險等同于她身上所有的奶牛的重量(當然不包括她自己)減去她的力量。你的任務是確定奶牛的順序，從而使得所有牛的風險中最大的一個盡量小。

Input

第1行：一個整數N 第2 . .N+ 1行: 兩個空格分隔的整數重量wi和力量si來描述奶牛i。

Output

一個整數，在所有牛的風險中最大的一個

Sample Input

3 10 3 2 5 3 3

Sample Output

2

Hint

樣例解釋: 把重量為10的牛放在底部。她將攜帶另外兩只牛，所以她的崩潰的風險是2 +3-3= 2。其他的奶牛有比她低的崩潰風險。

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; #define MAX 50000 struct Cow {int weight, strength;bool operator<(const Cow& other)const{//return other.weight<weight;return other.strength+other.weight<strength+weight;} }cow[MAX]; int main() {int N;while(cin>>N){int total = 0;for (int i=0;i<N;++i){scanf("%d%d",&cow[i].weight,&cow[i].strength);total+= cow[i].weight;}sort(cow,cow+N);int risk = 0x80808080;for(int i=0; i<N;++i){total-=cow[i].weight; // 減去自己的重量risk=max(risk,total-cow[i].strength); // 計算risk}cout <<risk<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的poj 3045 Cow Acrobats (贪心！！不是二分，)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。