相同耗电量下,优先跑要求电量高的;
相同要求电量下,优先跑耗电量低的;
不同耗电、不同要求电量下(如下👇),无法简单比较决定排序(排序做的不能AC的原因);
15:17、14:15 结果30 29-32
1:15、5:16 结果17 6-31
【为了解决这种情况】
进行简单推理:两个(a:b),(c:d),此时a!=c ;b!=d;
设电量为n (n>= max(b,d));
① 当n-a>=d 时,可以通过
所以 n_min = max(a+d, b);
当我们交换顺序 n_min = max(c+b,d);
所以为了让n最小化,我们排序的逻辑此时为:
max(a+d, b) < max(c+b, d) ? 【这么排(a,b)→(c,d)】 :【否则这样排(c,d)→(a,b)】;
【收尾】
排序策略写好了,我们在定义一个自定义排序函数即可,调用sort;
从头到尾贪婪计算电量即可;