题目

思路

• 贪心算法，利用推公式的办法进行形式化证明。
• 思考一种局部的情况，设第头牛的风险为，第头牛的风险为,如果这两头牛的位置进行交换，可以发现，原先第头牛现在的风险为，原先第头牛现在的风险为。换言之，原先第头牛的增量为：，原先第头牛的增量为。
• 4个数据当中，希望最大值最小，也就是希望和当中的最大值最小，如果交换之前的风险是小的，也就是这个关系必须成立。
• 所以可以依据的值从小到大进行排序，越小的越应该放在下面。

  代码

  ```cpp

  include

  include

  include

  include

using namespace std;

const int N = 5 * 1e5 + 5;

bool cmp (pair a, pair b) { return a.first + a.second < b.first + b.second; } int main() { pair nums[N]; int n = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> nums[i].first; cin >> nums[i].second; }

sort(nums, nums + n, cmp);
int sum[N];
memset(sum, 0, sizeof(sum));
for (int i = 1; i < n; i++) {
    sum[i] = sum[i - 1] + nums[i - 1].first;
}
int max_num = INT_MIN;
for (int i = 0; i < n; ++i) {
    max_num = max(max_num, sum[i] - nums[i].second);
}
cout << max_num << endl;
return 0;

} ```