Lflame

【2016/1/13考题】 小兵的故事

小兵的故事

(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

 

     大概就是前后门都可以影响答案,并且若前门(t1)确定时,后门(t2)对答案的影响满足单调性。

     而且可以得出t1,t2的取值最多分别只会有N、M个。 

     据此,考场上我只想到了O(log(N)*N^2),即枚举t1(O(N)),然后二分t2(O(log(N)))再check(O(N)),但是会TLE。

     对于这种题目 !  我们可以考虑t1和t2的性质 !  当t1增大时,t2只会减小 !

     故正解 : 枚举t1,用一个指针来做t2, 对于一对t1、t2用O(N)时间check。 

                    复杂度分析 : 枚举t1(O(N)) , t2最多移动O(N)次,故只会check O(N)次,总复杂度O(N^2)

评论

热度(1)