[洛谷P3512 [POI2010]PIL-Pilots]

题目链接：###

题目分析：###

感觉不是很难啊……不像是蓝题（AC量也不像）恶意评分？

少打了一个+1调了半天，就这样居然还能过60pts？我思路和题解第一篇高度重合是什么鬼啊，太过分了吧本来还想水篇题解的

单调队列分别维护序列最大值和最小值，如果极差\(>k\)的话就扔掉最大值和最小值里面靠前的那一个，因为你不能不改动这个连续子序列的左端点而从中间丢掉一个值。同时记录下这个序列的左端点\(last_l\)是扔掉的那个值的编号+1（只要丢掉这个值，剩下的序列就合法了），丢完之后更新\(ans=max(ans,i-last_l+1)\)即可。时间复杂度为\(O(n)\)。

其实是一道不错的单调队列题。

题做少了看什么题都感觉眉清目秀的

代码：###

#include<bits/stdc++.h>

#define N (3000000+5)

using namespace std;

inline int read(){

	int cnt=0,f=1;char c;

	c=getchar();

	while(!isdigit(c)){

		if(c=='-')f=-f;

		c=getchar();

	}

	while(isdigit(c)){

		cnt=cnt*10+c-'0';

		c=getchar();

	}

	return cnt*f;

}

int n,k,l1=1,r1=0,x,ans,l2=1,r2=0;

int last_l=1;

struct node{

	int dat;int pos;

} q1[N],q2[N];

int main(){

	k=read();n=read();

	if(n==1) {

		printf("1");

		return 0;

	}

	for(register int i=1;i<=n;i++){

		x=read();

		while(l1<=r1&&q1[r1].dat>x)r1--;

		q1[++r1].dat=x;q1[r1].pos=i;

		while(l2<=r2&&q2[r2].dat<x)r2--;

		q2[++r2].dat=x;q2[r2].pos=i;

		while(q2[l2].dat-q1[l1].dat>k){

			if(q1[l1].pos<q2[l2].pos&&l1<=r1){

				last_l=q1[l1].pos+1;

				l1++;

			}

			if(q1[l1].pos>=q2[l2].pos&&l2<=r2){

				last_l=q2[l2].pos+1;

				l2++;

			}

		}

		if(i-last_l+1>ans)ans=i-last_l+1;

	}

	printf("%d",ans);

	return 0;

}

巴特西

[洛谷P3512 [POI2010]PIL-Pilots]

题目链接：###

题目分析：###

代码：###

最新文章

热门文章