题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.*;
class Main{
public static void main(String[] args) {
// 我们把wi + si > wi1 + si1 的可以交换不会得到更差结果 也就是wi + si大的放在下面 所以我们可以一直交换吧wi + si大的放下面
// 假设 i1 头牛 wi1 si1 i + 1头牛 wi2 si2 wi1 + si1 > wi2 + si2 可以的到wi1 - wi2 + si1 - si2 > 0
// i 的风险 i + 1 的风险
//1 w1 + w2 + .. wi0 - si1 2 w1 + w2 + .. + wi0 + wi1 - si2 交换前
//3 w1 + w2 + …wi0 - si2 4 w1 + w2 + … wi0 + wi2 - si1 交换后
// 我们来看看这两头牛中的最大的风险 对比2 3 2 - 3 = wi1 > 0 2比3风险一定大 然后看2 - 4 = wi1 - s12 - wi2 + si1 > 0
// 也就是2 风险大于4的风险 所以如果不交换 第i + 1头牛的风险是一定大于 交换后第i 第i + 1投牛的风险
// (只知道贪心后最大风险) >= 交换后最大风险 (交换前最大风险来源 其他的牛 或者第i头牛 第i + 1头牛
// 如果最大风险如果来源于i + 1头牛 交换后 就不存在了 如果最大风险来自其他牛 交换后没区别但没变差 如果来自i头牛
// 那么你想 2 < 1 3 4 都小于2 交换后1 也不存在了 变成3 4 是不是最大风险变小了 如果2 > 1 那么1显然无用 我们只关注最大风险
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[n][3];
for (int i = 0; i < n; i) {
nums[i][0] = sc.nextInt();
nums[i][1] = sc.nextInt();
nums[i][2] = nums[i][0] + nums[i][1];
}
Arrays.sort(nums, (a, b) -> Integer.compare(a[2], b[2]));
// 某个方法可能使的 个别的牛风险小 但是会使得其他牛的风险值大 要一个方法最平均使的所有牛的都风险都小 其中最大的相对其他方案小
int res = Integer.MIN_VALUE; // 是找一个方案使得 使得所有奶牛的风险值中的最大值尽可能的小。 确实很像二分的提示
int sum = 0;
for (int i = 0; i < n; i) {
res = Math.max(res, sum - nums[i][1]);
sum += nums[i][0];
}
System.out.print(res);
}
}