题目链接:传送门

Description

一个长度为L的圈,有n个人在上面跑,每个人的起始位置为di,速度为vi,且起始位置和速度均不相同,每个人有力量值wi,如果一个人遇到力量值比自己大的,则这个人会被标记,直到不会有人再被标记时将会停止,问这个过程总共花费多少时间

Solution

CDQ分治 设2个人的起始位置为d1和d2,d1 < d2,设时间为t,如果这2个人相遇,则一定会有

TeX parse error: Undefined control sequence \*

TeX parse error: Undefined control sequence \*

因此可以二分时间,记录时间t下每个人跑的距离dis[i],按照起始位置从小到大排序,分治时按照力量值w从大到小排序,归并时记录左右两边

TeX parse error: Undefined control sequence \*

的最小值L1,L2和最大值R1,R2。对于左分治区间[l,m]的每个人,如果

TeX parse error: Undefined control sequence \[

TeX parse error: Undefined control sequence \[

则将它标记;对于右分治区间

TeX parse error: Undefined control sequence \[

的每个人,如果

TeX parse error: Undefined control sequence \[

TeX parse error: Undefined control sequence \[

则将它标记;如果存在人的力量值不是最大的且这个人没有被标记,则返回false,并记录他为最后一个要被标记的人last

Code

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 1e6 + 10;
const double inf = DBL_MAX, eps = 1e-14;

int N, L;
struct node
{
int d, v, w, id;
double dis;
}A[Maxn], p[Maxn], tmp[Maxn];

inline int cmp (node a, node b)
{
return a.d < b.d;
}

int Max, last, Vis[Maxn];

inline void Solve (int l, int r)
{
if (l >= r) return ;
int mid = (l + r) >> 1;
Solve (l, mid);
Solve (mid + 1, r);
int p1 = l, p2 = mid + 1, p3 = l;
double L1 = inf, L2 = inf, R1 = -inf, R2 = -inf;
double TL1 = inf, TL2 = inf, TR1 = -inf, TR2 = -inf;
while (p1 <= mid || p2 <= r)
{
if (p2 > r || (p1 <= mid && p[p1].w > p[p2].w))
{
if (p3 > l && tmp[p3 - 1].w > p[p1].w)
L1 = TL1, R1 = TR1, L2 = TL2, R2 = TR2;
if (L2 <= p[p1].dis || R2 - L >= p[p1].dis)
Vis[p[p1].id] = 1;
TL1 = min(TL1, p[p1].dis);
TR1 = max(TR1, p[p1].dis);
tmp[p3++] = p[p1++];
}
else
{
if (p3 > l && tmp[p3 - 1].w > p[p2].w)
L1 = TL1, R1 = TR1, L2 = TL2, R2 = TR2;
if (L1 + L <= p[p2].dis || R1 >= p[p2].dis)
Vis[p[p2].id] = 1;
TL2 = min(TL2, p[p2].dis);
TR2 = max(TR2, p[p2].dis);
tmp[p3++] = p[p2++];
}
}
for (int i = l; i <= r; ++i)
p[i] = tmp[i];
}

inline int Check (double x)
{
for (int i = 1; i <= N; ++i)
{
p[i] = A[i], Vis[i] = 0;
p[i].dis = p[i].d + x * p[i].v;
}
Solve (1, N);
for (int i = 1; i <= N; ++i)
if (!Vis[i] && A[i].w != Max)
{
last = i;
return 0;
}
return 1;
}

inline void update (node a, node b, int &ans1, int &ans2)
{
if (a.v < b.v) swap(a, b);
LL x = a.v - b.v, y;
if (a.d < b.d) y = b.d - a.d;
else y = L - a.d + b.d;
if (y * ans1 <= x * ans2) ans1 = x, ans2 = y;
}

int main()
{
#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
int T;
scanf("%d", &T);

while (T--)
{
scanf("%d%d", &N, &L);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i].d);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i].v);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i].w);
sort(A + 1, A + N + 1, cmp);
for (int i = 1; i <= N; ++i) A[i].id = i;

Max = 0;
for (int i = 1; i<= N; ++i)
Max = max(Max, A[i].w);

double l = 0, r = L;
last = 0;

while (l + eps < r)
{
double mid = (l + r) / 2;
if (Check (mid)) r = mid;
else l = mid;
}
if (!last)
{
cout<<0<<endl;
return 0;
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= N; ++i)
if (A[i].w > A[last].w)
update(A[i], A[last], ans1, ans2);
cout<<ans2 / __gcd(ans1, ans2)<<"/"<<ans1 / __gcd(ans1, ans2)<<endl;
}
return 0;
}