本文迁移自洛谷原文。
一道较为简单的双指针
每次维护左边的人走到那个旗子，右边的人走到那个旗子，慢慢向中间不断更新靠拢即可。
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
| #include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int n,m;
ld len;
ld a[mxn];
inline void solve(){
cin>>n>>len;
for(int i=1;i<=n;++i)cin>>a[i];
int l=1,r=n;
ld cl=0,cr=len;
ld sl=1,sr=1;
ld ans=0;
for(;l<=r;){
ld dl=a[l]-cl,dr=cr-a[r];
ld tl=dl/sl,tr=dr/sr;
if(tl<tr){
cl=a[l];
cr-=tl*sr;
ans+=tl;
sl=sl+1;
++l;
}else{
cr=a[r];
cl+=tr*sl;
ans+=tr;
sr=sr+1;
--r;
}
}
ans+=(cr-cl)/(sl+sr);
cout<<fixed<<setprecision(9)<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;cin>>T;
for(;T--;)solve();
}
|