毕业照

watersail / 2024-09-05 / 原文

只考虑第三问
跳k段可以通过倍增优化，问题转化为，从任意一个点开始，跳1段最多能到哪个点，这是倍增的基础
可以用双指针求，退一步讲，就算你没想到双指针，二分+st表（倍增实现，但不需要跳，首尾闭环O(1)求任意区间最值）也应当可以O(nlogn)地求出来
这里面暗含了预处理的思想，把那些计算【提前】处理
真的难以理解为什么考场上的你会做不出来这样一道题目，是心态问题吗？无论如何，不要陷于泥沼

点击查看代码

#include <bits/stdc++.h> 
using namespace std;
int h[500005],f[500005][19];
multiset<int>s;
int n,k,d,ans;
bool check(int l)
{
	int maxn=h[1],minn=h[1],cnt=1;
	for(int i=2;i<=n;i++)
	{
		if(abs(maxn-h[i])<=l&&abs(minn-h[i])<=l)
		{
			maxn=max(maxn,h[i]);
			minn=min(minn,h[i]);
		}
		else
		{
			cnt++;
			maxn=minn=h[i];
			if(cnt>k)
			{
				return false;
			}
		}
	}
	return true;
}
int solve()
{
	int maxn=h[1],minn=h[1],cnt=1;
	for(int i=2;i<=n;i++)
	{
		if(abs(maxn-h[i])<=d&&abs(minn-h[i])<=d)
		{
			maxn=max(maxn,h[i]);
			minn=min(minn,h[i]);
		}
		else
		{
			cnt++;
			maxn=minn=h[i];
		}
	}
	return cnt;
}
int maxn()
{
	multiset<int>::iterator it;
	it=--s.end();
	return *it;
}
int minn()
{
	multiset<int>::iterator it;
	it=s.begin();
	return *it;
}
void pre()
{
	for(int j=1;j<=18;j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(f[i][j-1]==n)
			{
				f[i][j]=n;
			}
			else
			{
				f[i][j]=f[f[i][j-1]+1][j-1];
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin>>n>>k>>d;
    for(int i=1;i<=n;i++)
    {
    	cin>>h[i];
    }
    int l=0,r=1e9-1;
    while(l<r)
    {
    	int mid=(l+r)>>1;
    	if(check(mid))
    	{
    		r=mid;
    	}
    	else
    	{
    		l=mid+1;
    	}
    }
    cout<<l<<endl;
    cout<<solve()<<endl;
    l=0,r=0;
    s.insert(h[0]);
    while(l<n)
    {
    	multiset<int>::iterator it;
    	it=s.find(h[l]);
    	s.erase(it);
    	l++;
    	while(r<n&&(s.empty()||abs(maxn()-h[r+1])<=d&&abs(minn()-h[r+1])<=d))
    	{
    		r++;
    		s.insert(h[r]);
    	}
    	f[l][0]=r;
    }
    pre();
    for(int i=1;i<=n;i++)
    {
    	int st=i,ed=i;
    	for(int j=0;j<19;j++)
    	{
    		if(((k>>j)&1)==1)
    		{
    			ed=f[ed][j]+1;
    			if(ed>n)
    			{
    				break;
    			}
    		}
    	}
    	ans=max(ans,ed-st);
    }
    cout<<ans<<endl;
    return 0;
}