二分答案玄关求调
查看原帖
二分答案玄关求调
1050021
likezheng2023楼主2024/5/15 21:41
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	register int x=0,f=0;register char c=getchar();
	while(c<'0'||c>'9')f=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return f?-x:x;
}
int n,m,p,pos,finaltime,nowhere[2000000];
int op[20000000],qian[20000000];
int fina[20000000];
struct node
{
	int w,wh;
}a[2000000];
struct node2
{
	int l,r;
}may[2000000];
int tot;
bool check(int num)
{
	int tt;
	for(int l=max(pos-num+1,1ll);l<=pos&&l+num-1<=n;l++)
	{
		int r=l+num-1;
		int xz=(a[r].w-a[l].w)*2;
		if(l<=p&&p<=r)tt=m+5;
		else tt=m;
		if(xz<=tt)return 1;
	}
	return 0;
}

bool cmp(node x,node y)
{
	return x.w<y.w;
}
signed main()
{
	for(int i=0;i<=n+10;i++)fina[i]=3e18;
	n=read(),m=read(),p=read();
	for(int i=1;i<=n;i++)a[i].w=read(),a[i].wh=i;
	a[++n].w=0;a[n].wh=n;
	sort(a+1,a+1+n,cmp);
	pos=1;
	while(a[pos].wh!=n)pos++;
	int l=0,r=n,mid;
	int ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans-1<<'\n';
	for(int left=max(pos-ans+1,1ll);left+ans-1<=n&&left<=pos;left++)
	{
		int	right=left+ans-1;
		int tt=(left<=p&&p<=right)?m+5:m;
		if((a[right].w-a[left].w)*2<=tt)may[++tot]={left,right};
	}
	for(int i=1;i<=n;i++)nowhere[a[i].wh]=i;
	int ll=1,rr=tot;
	for(int i=1;i<n&&ll<rr;i++)
	{
		int  np=nowhere[i];
		if(np<may[ll].l||np>may[rr].r)continue;
		while(may[ll].r<np)ll++;
		while(may[rr].l>np)rr--;
	}
	for(int i=may[ll].l;i<=may[ll].r;i++)
	{
		if(a[i].wh!=n)cout<<a[i].wh<<' ';
	}
	return 0;
}
2024/5/15 21:41
加载中...