E. Two Platforms
题意
在二维直角坐标中给出n个球的坐标
以及两块长为k的板子 要求在二维平面中平行于x轴放置两块板子
n个球垂直于x轴落下
问这两个板子接到最多几个球
题解
参考题解
实际上我们只关心n个球的x坐标
于是对n个球的x坐标排序
显然球落到板子边界时可能存在最优解
于是我们设计dp
求出第i个球落到一块板子的右端点时 这个板子最多能接住几个球
记L[i]作为记录从第1个点到第i个点之间长度为k的平台能保存的最多的点
求出第i个球落到一块板子的左端点时 这个板子最多能接住几个球
记R[i]作为记录从第n个点往前到第i个点之间长度为k的平台能保存的最多的点数
于是最后答案为ans=max(ans,L[i]+R[i+1])
由于L[i]是以第i个球作为右端点 R[i+1]以第i+1个点为左端点
所以i和i+1个球有同一个x (重叠) 也不会重复统计
对求出第i个球落到一块板子的左/右端点时 这个板子最多能接住几个球
这个问题可以用单调队列解决
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
| #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;
const double Pi=acos(-1);
const ll Mod=1e9+7;
ll x[Max],L[Max],R[Max];
int main(){
Turnoff;
int t;cin>>t;
while(t--){
int n,k,y;cin>>n>>k;
for(int i=0;i<n;i++)cin>>x[i];
for(int i=1;i<=n;i++)cin>>y;
sort(x,x+n);
queue<int>q;
for(int i=0;i<n;i++){
if(!q.empty()&&q.front()<x[i]-k)q.pop();
q.push(x[i]);
L[i]=q.size();
if(i>0)L[i]=max(L[i],L[i-1]);
}
while(!q.empty())q.pop();
for(int i=n-1;i>=0;i--){
if(!q.empty()&&q.front()>x[i]+k)q.pop();
q.push(x[i]);
R[i]=q.size();
if(i<n-1)R[i]=max(R[i],R[i+1]);
}
R[n]=0;ll ans=0;
for(int i=0;i<n;i++)ans=max(ans,R[i+1]+L[i]);
cout<<ans<<endl;
}
}
|