巨石滚滚(牛客算法入门第一节课后题) 巨石滚滚(牛客算法入门第一节

巨石滚滚帕秋莉掌握了一种土属性魔法
【巨石滚滚(牛客算法入门第一节课后题)】她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
输入描述:

输入一个整数T，代表T组数据，每组数据中：前一行两个整数n , m，表示障碍个数和土球的稳定性接下来一行两个整数，分别表示障碍的ai和bi

输出描述:

若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)

示例1
输入复制

1 5 50 49 49 52 0 5 10 26 24 70 70

输出复制

No

备注:

Σn <= 500000, 1<=m<=100000,0<=a,b<=100000

大致做法就是贪心，排序。然后模拟。
这道题最大的问题就是 Comparable比较器条件如何写，它要满足，回馈-损失最大，并且这个差值为正数的时候，损失最小的要排在前面，这个差值为负数时，价值最大的要排在前面，所以比较条件不止一个

//key为损失价值，value为回馈价值，m为两者的差值 //自定义的比较器(比较规则) @Override public int compareTo(Boo2 o) { //冲撞回馈后为正价值,按照损失小的排前面 if(this.m>=0&&o.m>=0) return (int) (this.key-o.key); //冲撞回馈后为负价值,按照价值大的排前面 if(this.m<0&&o.m<0) return (int) (o.value-this.value); //否则回馈-冲撞大的排前面 return (int) (o.m-this.m); }

详细代码：

/** * 测试数据 1 5 50 20 40 80200 30104 3322 100 5 */import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class 巨石滚滚 { static Boo2[] arr=new Boo2[(int) (5e5+10)]; static long t,m; static int n; //java的快读 static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static long nexlong() throws IOException {in.nextToken(); return (long) in.nval; }public static void main(String[] args) throws IOException { t=nexlong(); n1: while (t-- >0){ n= (int) nexlong(); m=nexlong(); for (int i = 1; i <=n; i++) { long a=nexlong(); long b=nexlong(); //读入损失，回馈，和差值存放在外部类里面 arr[i]=new Boo2(a,b,b-a); } //外部类里面重写了比较器这里sort一下 //注意这个比较器是这道题的重点 Arrays.sort(arr,1, n+1); //模拟一下 for (int i = 1; i <=n; i++) { //根据题意判断 if(m>arr[i].key) m=m-arr[i].key+arr[i].value; else { System.out.println("No"); continue n1; } }System.out.println("Yes"); } }} class Boo2 implements Comparable{ long key; long value; long m; Boo2(long key,long value,long m){ this.key=key; this.value=https://www.it610.com/article/value; this.m=m; }@Override public String toString() { return"Boo2{" + "key=" + key + ", value="https://www.it610.com/article/+ value +'}'; } //自定义的比较器(比较规则) @Override public int compareTo(Boo2 o) { //冲撞回馈后为正价值,按照损失小的排前面 if(this.m>=0&&o.m>=0) return (int) (this.key-o.key); //冲撞回馈后为负价值,按照价值大的排前面 if(this.m<0&&o.m<0) return (int) (o.value-this.value); //否则回馈-冲撞大的排前面 return (int) (o.m-this.m); } }