20160113 考题 小兵的故事
小兵的故事
（bin.cpp/c/pas）
Time limited = 1500ms
小兵休息时喜欢打打炉石和刀塔，然而这在伟大的计算机房是不怎么允许的。
已知伟大的计算机房有两个房门:前门和后门。
这两个门都有着高超的科技，可以设定一个参数t。z
如果一个人会在T1时刻进来，那么就会在T1-t时刻把门打开，
但是如果下一个人在T2时刻进来：
（1）如果该T2-T1<=2t，那么门会在T2+t时刻关上
（2）否则，会先在T1+t时刻关上，T2-t时刻打开，T2+t时刻再关上。
如果两个门同时打开的时间超过d（一旦有任意一个门关上则重新计算），那么就会形成冷空气对流，小兵就会感觉到寒冷，高超的操作就会受到影响。
如果两个门开关的次数太多，就增加了被查房的风险。
小兵现在已经预测出午休时间两个门分别会在哪些时刻进来人，现在问题是如何设定前门和后门的两个参数:t1、t2（必须是>=1的整数）使得：
1、两个门同时打开的时间不超过d（一旦有任意一个门关上则重新计算）
2、两个门的打开的次数之和尽可能的小
输入描述:
第一行三个整数N，M，d
第二行N个整数，p1<p2<…<pN，表示前门会在哪些时刻进来人
第三行M个整数，q1<q2<…<qM，表示后门会在哪些时刻进来人
d,p,q<=10^9
10% N,M<=50
30% N,M<=500
100% N,M<=5000
输出描述：
一个整数Ans，表示两个门打开的次数之和。如果无解输出”No solution”（不包括引号。
输入样例：
3 2 4
1 6 13
7 11
输出样例：
3
题解：
1.首先我们会发现t1和t2只有5000种取值，为什么，考虑对于一个pos[i],pos[i-1]，如果要让他们之间不关门最小的dis是
[(pos[i]-pos[i-1]/)2] 上取整，如果我们现在拿到的这些dis是1 2 3 5，那么选择4并没有什么用反而无故延长开门时间，还不如选3。
所以只有这5000种取值。
2.假设此时t1和t2已经顶了d，我们发现当t1增大，t2不会变大（变大了吹风时间会变多，就变得不合法）
那么我们发现其实就是单调的，
t1和t2是可以O(n+m)扫的，然后check就O(n+m),所以时间复杂度总的来说是O((n+m)^2)
嗯非常巧的是std给的1.5s，结果开了2.5s都还是T三个点（然后被yjq怒虐），电子坑大真是令人无语。代码就不贴了（开了O2才过不然和std下场一样的人捂脸）