D. New Passenger Trams
题意：
某个星球的一天有h小时，一小时有m分钟，现在有两种车要开，客色的每半小时开一次，每次要等待k(k<=m/2)分钟再开。货车有固定的时刻表，且没有准备时间，但是它与客车的等待时间重合了就会被取消掉（端点重合不取消），问你第一辆客车车的出发时间t(t<=m/2)是多少才能使最少的货车被取消。输出最少要取消几辆以及第一辆客车的出发时间和被取消的货车是那几班
题解
事实上由于每个客车半小时发一趟车，客车每小时只会出发两趟 所以客车从到站到出发的时间段实际上是以半小时为周期的, 在一小时60分种的情况下若下一趟的车在20分到 后40出发 即相当于 0到30分中 [20,30]和[0,10]分中有客车在等待 货车不能发车，所以将所有的货车出发时间映射到同一个半小时时间段内 仅仅讨论这半个小时内 哪段长度为k(客车等待时间)的时间段内所覆盖到的货车发车班次最少即最优解将所有货车映射到同一个半小时内后 第l趟货车和第r趟货车若发车间隔>=k那么它们就不会被同一个客车等候时间被取消，我们要通过双指针得到一个区间左右端点上货车发车间隔<k且最少货车发车的时间段确定了这个时间段后，第一班客车发车的时间t=右端点r位置的货车发车时间 因为经验上,客车到站或出站与某一辆货车的发车时间重合时可以取到最优 (突变点)
这里train[n+1]=train[1]+m/2 目的是为了更好的处理客车等候时长由于取模(环变链)导致的连续区间分裂 这样双指针就不会因为时长为k的区间一半在前一半在后而变得复杂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
struct Train{
ll mi;
int indx;
} train[Max];
ll n,h,m,k,half;
bool cmp(Train x,Train y){return x.mi<y.mi;}
int main() {
Turnoff;
cin>>n>>h>>m>>k;half=m/2;
for(int i=0;i<n;i++){
int hi,mi;cin>>hi>>mi;
train[i].mi=mi%half;
train[i].indx=i+1;
}
sort(train,train+n,cmp);
for(int i=0;i<n;i++){
train[i+n].mi=train[i].mi+half;
train[i+n].indx=train[i].indx;
}
ll bios;
int num=2e5;
for(int l=0,r=n;r<2*n;r++){
while(train[r].mi-train[l].mi>=k)l++;
if(num>r-l){
num=r-l;
bios=train[r].mi;
}
}
cout<<num<<" "<<bios%half<<endl;
for(int i=0;i<2*n;i++){
if(train[i].mi<bios&&train[i].mi>bios-k)cout<<train[i].indx<<" ";
}
cout<<endl;
}
|