牛客算法竞赛入门课第一节习题Part1（切长条~「土」巨石滚滚）

题意：

给若干条线段，可以在任意一行做一条竖线，问至少做几条竖线才能把每一条线段都切开。

思路：

显而易见的贪心思路。

按照关键字为每条线段的左端点进行从小到大的排序，对于一个新的线段，如果他的左端点的值大于等于在前几条线段的右端点的最小值，那么就不能跟前面的重合，需要多做一条竖线，否则就更新右端点的最小值。

代码：

题意：

她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍

土球有一个稳定性x，如果x < 0，它会立刻散架

每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性

帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？

思路：

总思路就是贪心，排序之类的。

但是贪心的过程就显得很繁琐。

首先对于每个障碍有两个属性，一是使土球的稳定性造成a[i]的减少，二是使土球的稳定性造成b[i]的增加。

因为土球的稳定性小于0就会散架，所以我们肯定会优先考虑那些能够给土球增加稳定性的操作，即先按照稳定性的净增加量从大到小排序。

如果可以增加稳定性的话，就优先选择对稳定性的损耗最小的，即再按照稳定性的消耗量从小到大排序。

如果只能消耗稳定性的话，就优先选择增加稳定性多的，即按照增加量从大到小排序。

最后再遍历统计就好了，但是要注意的是，一旦稳定性<0，就会立刻散架~

代码：