题目链接

题意：

在一个平面上有n个点，放置两个长度为k的水平平台，n个点一直下降（y坐标减少），如果降到平台上，该点将会被保存，求怎样放置这两个平台，使保存的点最多。

思路：

由题可知，降在平台上的点与y坐标没关系，只要使用x坐标，将点按x坐标排序，求出以第i个点的x坐标为右端点长度为k的平台能保存的点的数量，数组l[i]记录从第1个点到第i个点之间长度为k的平台能保存的最多的点。

求出以第i个点的x坐标为左端点长度为k的平台能保存的点的数量，数组r[i]记录从第n个点往前到第i个点之间长度为k的平台能保存的最多的点数。

答案就是遍历n个点，找到l[i]+r[i+1]的最大值。

代码

 

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn=1e6+10;
 6 
 7 int x[maxn],l[maxn],r[maxn];
 8 void solve()
 9 {
10     int n,k;
11     scanf("%d %d",&n,&k);
12     for(int i=0; i<n; i++)
13         scanf("%d",&x[i]);
14     int y;
15     for(int i=0; i<n; i++)
16         scanf("%d",&y);
17     sort(x,x+n);
18     queue<int>q;
19     for(int i=0; i<n; i++)
20     {
21         if(!q.empty()&&q.front()<x[i]-k)
22             q.pop();
23         q.push(x[i]);
24         l[i]=q.size();
25         if(i>0)
26             l[i]=max(l[i],l[i-1]);
27     }
28     while(!q.empty())
29         q.pop();
30     for(int i=n-1; i>=0; i--)
31     {
32         if(!q.empty()&&q.front()-k>x[i])
33             q.pop();
34         q.push(x[i]);
35         r[i]=q.size();
36         if(i<n-1)
37             r[i]=max(r[i],r[i+1]);
38     }
39     int ans=0;
40     l[n]=r[n]=0;
41     for(int i=0; i<n; i++)
42         ans=max(ans,l[i]+r[i+1]);
43     printf("%d\n",ans);
44 }
45 signed main()
46 {
47     int _;
48     cin>>_;
49     while(_--)
50         solve();
51     return 0;
52 }