暑假集训测试（一）题解
1、排版
　　模拟算法：每读入一个单词，确定是输出到当前行，还是下一行。

　　首先输出第一个单词s，并设当前行的字符数为cnt=s.size()

　　从第二个单词开始，每读入一个单词s，都先判定cnt+s.size()<=m，
　　　若成立则输出到当前行，即cout<<" "<<s;
　　　否则输出到下一行：cout<<'\n'<<s；且 cnt=s.size()。
　　时间复杂度：O(n)

2、排列游戏

　　题意理解：q是1~n的排列，所以q中的元素各不相同，则都是1~n中一个数字。

　　枚举算法：枚举排列 p 的第一项，设为p[1]=x（1~n），则可根据q来推算后面的各项：
　　　　p[2] = q[1] - p[1]
　　　　p[3] = q[2] - p[2]
……
　　若推算到某一项p[i]=q[i]-p[i]时，p[i]在之前出现过（标记数组），则枚举的x不合适，继续枚举下一个x。

　　时间复杂度：O(n^2)

3、拉力赛

　　贪心算法：要想尽快完成比赛，需要最高速度最大。

　　所以解题思路：就是枚举可能的最高速度：

　　算法1、 顺序枚举

　　　1、特判：从0开始加速，还没加速到x就走完全程S，此时直接输出加速的时间即可!

　　　2、加速到x都还没有走完，还需继续加速（当前速度v=x）：
　　　　最高速度每增加 1，即 v++，若此时走的最短路程s<S+x，则说明可以增加， 直到>=S+x为止

　　　3、在最高速度为 v 时，计算答案：

　　　　全加速时间 + 全减速时间 + 以最高速行驶时间 + 可能多余的1秒（小于最高速的速度行驶1秒）

　　时间复杂度：O(sqrt(S))

算法2、二分枚举

　　1、同样特判：如果全加速走完速度都不会超过x，
　　　计算答案：1+2+..+t>=K，求t的最小的t

　　2、应该先加速到超过x，然后在减速到x：
　　　2.1 二分答案求最大速度maxv,验证条件，
　　　只要全加速的路程+全减速路程小于K+x,就是合适的.

　　　2.2 计算答案：
　　　全加速时间+全减速时间+以最高速行驶时间+可能多余的1秒

　　时间复杂度：O(log(S))

4、排队观察
　　思路：枚举记录 i = 1..M，对于每个 i，如何判定前i条记录是否都正确呢？

　　如果把每个学生看成图一个顶点，按记录的意义，某同学在那些同学前面可以建立有向边，如果前i条记录正确，则建立的图一定是DAG图，于是用拓扑排序即可。

　　优化枚举：可以用二分答案枚举i，答案范围：1..M，所以二分答案框架如下：

　　int l=0,r=M,mid,ans=0;
　　while(l<=r){
　　　　mid=(l+r)/2;
　　　　if(check(mid))
　　　　　　　ans=mid,l=mid+1;
　　　　else
　　　　　　r=mid-1;
　　}

　　bool check()功能：检查前mid条记录是否正确，先建立有向图的存储结构，在用拓扑排序检查是否是有向图。

　　时间复杂度：O((N+E)logM)，其中E是DAG图的边的数目。