E. Two Platforms

https://codeforces.com/contest/1409/problem/E

思路：开始自己想前缀和预处理，找一段长度-2*k的最小和，然后想到这个可以是不连续的。所以直接处理两个板子。

先考虑枚举，以当前位为板子起点，往右最多能到(pos)多少（由于单调的，所以二分可以，尺取法去找也可以）。这时候第二个板子应该放哪呢？放从Pos+1开始?还是pos+2...？这里就又有一个枚举的过程了。应该放后缀最大的点。所以先预处理pre[i]，处理完后预处理suf_max[i]=max(suf_max([i+1],pre[i]) 【这个点到后面一段能覆盖的最大值是多少】

最后O(N)和一起来枚举处理。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+100;
typedef long long LL;
void solve()
{
	LL n,k;cin>>n>>k;
	vector<LL>x;
	for(LL i=0;i<n;i++){
		LL _x;cin>>_x;x.push_back(_x);
	}
	for(LL i=0;i<n;i++){
		LL y;cin>>y;
	}
	sort(x.begin(),x.end());
	vector<LL>can;
	for(LL i=0;i<n;i++)
	{
		LL it=upper_bound(x.begin(),x.end(),x[i]+k)-x.begin();
		can.push_back(it-i);
	}
	vector<LL>suf_max(n+10);
	for(LL i=n-1;i>=0;i--)
	{
		suf_max[i]=max(suf_max[i+1],can[i]);
	}
	LL ans=-0x3f3f3f3f;
	for(LL i=0;i<n;i++)
	{
		ans=max(ans,can[i]+suf_max[can[i]+i]);
	}
	cout<<ans<<endl;

}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--)
  {
  	solve();
  }
return 0;
}

最后

以上就是柔弱小霸王为你收集整理的E. Two Platforms的全部内容，希望文章能够帮你解决E. Two Platforms所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。