牛客算法竞赛入门课第一节习题Part1（切长条~「土」巨石滚滚）
牛客算法竞赛入门课第一节习题Part1（切长条~「土」巨石滚滚）
切长条（贪心）
题意：
给若干条线段，可以在任意一行做一条竖线，问至少做几条竖线才能把每一条线段都切开。
思路：
显而易见的贪心思路。
按照关键字为每条线段的左端点进行从小到大的排序，对于一个新的线段，如果他的左端点的值大于等于在前几条线段的右端点的最小值，那么就不能跟前面的重合，需要多做一条竖线，否则就更新右端点的最小值。
代码：
「土」巨石滚滚
题意：
她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
思路：
总思路就是贪心，排序之类的。
但是贪心的过程就显得很繁琐。
首先对于每个障碍有两个属性，一是使土球的稳定性造成a[i]的减少，二是使土球的稳定性造成b[i]的增加。
因为土球的稳定性小于0就会散架，所以我们肯定会优先考虑那些能够给土球增加稳定性的操作，即先按照稳定性的净增加量从大到小排序。
如果可以增加稳定性的话，就优先选择对稳定性的损耗最小的，即再按照稳定性的消耗量从小到大排序。
如果只能消耗稳定性的话，就优先选择增加稳定性多的，即按照增加量从大到小排序。
最后再遍历统计就好了，但是要注意的是，一旦稳定性<0，就会立刻散架~
代码：
投递小米集团等公司10个岗位 >
