AcWing 125. 耍杂技的牛_Java版本
原题链接
中等
作者:
越自律越自由
,
2020-05-18 14:53:13
,
所有人可见
,
阅读 682
import java.util.*;
/*
反证法证明:wi+si从小到大排序可以得到最大风险值的最小可能值
假设wi+si>w(i+1)+s(i+1),此时
第i个位置的牛 第i+1个位置的牛
交换前的风险值 w1+w(i-1)-si w1+w(i-1)+wi-s(i+1)
交换后的风险值 w1+w(i-1)-s(i+1) w1+w(i-1)+w(i+1)-si
对上面式子+si+s(i+1)-(w1+w(i-1)),可得
第i个位置的牛 第i+1个位置的牛
交换前的风险值 s(i+1) wi+si
交换后的风险值 si w(i+1)+s(i+1)
此时交换后的最大风险值为Math.max( si,w(i+1)+s(i+1) ),这两个值均小于wi+si,
说明交换后的最大风险值反而变小了,所以原假设不成立
*/
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] w=new int[n];
int[] s=new int[n];
List<Pairs> list=new ArrayList<>();
for(int i=0;i<n;i++){
w[i]=sc.nextInt();
s[i]=sc.nextInt();
list.add(new Pairs(w[i],s[i]));
}
//按照升序排序
//stream()函数把集合装成流,可以多次使用这个集合,若不转换,则只能使用一次
//sorted()排序函数,默认是升序,
//中间传入Comparator是用于对集合排序的类,comparing函数里写入排序的依据( 集合::get属性() )
//collect是一个终端操作,它接收的参数是: 将流中的元素累积到汇总结果的各种方式
//Collectors.toList()把流中所有元素收集到list中,需引入其前缀:java.util.stream.
list=list.stream().sorted(Comparator.comparing(Pairs::getSum)).collect(java.util.stream.Collectors.toList());
//对res赋值为第一个结果-s,sum用于保存w1+w2..w(i-1)
int sum=0,res=-list.get(0).getS();
for(int i=1;i<n;i++){
sum=sum+list.get(i-1).getW();
res=Math.max(res,sum-list.get(i).getS());
}
System.out.println(res);
}
}
//用于保存并排序数据
class Pairs{
int w;
int s;
//因为用sum排序,特此额外建立一个成员变量
int sum;
Pairs(int l,int r){
w=l;
s=r;
sum=s+w;
}
public int getW(){
return w;
}
public int getS(){
return s;
}
public int getSum(){
return sum;
}
}
如有错误,欢迎指正