lkMiles

退役oier

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下场一样的人捂脸)

评论
©lkMiles
Powered by LOFTER