反读人兮逼傻我也

        “一万吨木头重还是一万吨铁重？“，如果有人想都不想地回答道：”铁重“，那大家肯定哄堂大笑。但仔细想一想，铁重、木头重都有道理，但一样重反而是没有道理的。
        铁重，是在这样的假设下的：木头和铁的质量的的确确都是一吨（尽管在空气中，这一点比较难以做到）。那么受到空气浮力的影响，铁会比木头轻。具体轻多少呢？根据阿基米德原理，固体在流体中受到的浮力大小等于它排开的流体受到的重力。设F铁、F木分别为铁、木头受到的浮力，有

我的思路：

        一开始我的想法是，从一个城市出发，一直选择最近的城市，并把数轴上两城市之间的区域染色。后来发现这样下去越来越复杂，肯定不对。于是我又换了个思路，考虑两条道路(n, p), (n+1, q)不交叉时满足的条件：p < q ，也就是说，如果把计划修路的一端从小到大排序，要求的就是另一端点的编号序列之最长上升子序列。
        这个最长上升子序列，我有点陌生。想了十分钟才想起来我当时的思路：每添加进来一个数，就往前搜，看看从哪个比当前元素小的元素“接”过来序列最长——或者一个都不接。这个算法正确但超时。（虽然我确定N方的算法在五十万的数据量面前一定超时，但还是忍不住写了一遍，提交了一下）这就意味着应该用一个数组存“种子元素”而非长度。