玄关,提问(已过)
查看原帖
玄关,提问(已过)
1237546
Langke_Saonian楼主2024/8/8 10:28

有人能指导一下为什么按第一种写法过了,第二种不行(区别:INF的大小)

#include<bits/stdc++.h>
using namespace std;


template<typename type>
inline void read(type &x){
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1){
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}


#define INF 0x3f3f3f3f
deque<int> minn,maxx;
int n,s,l,c;
int a[100005],dp[100005]; 
inline int query(){
	while(!minn.empty()&&minn.front()<c+1) minn.pop_front();
	while(!maxx.empty()&&maxx.front()<c+1) maxx.pop_front();
	return a[maxx.front()]-a[minn.front()];
}
int main(){
	memset(dp,0x3f,sizeof(dp));
	read(n),read(s),read(l);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	dp[0]=0;
	for(int i=1;i<=n;i++){
		while(!minn.empty()&&a[minn.back()]>=a[i]) minn.pop_back();
		minn.push_back(i);
		while(!maxx.empty()&&a[maxx.back()]<=a[i]) maxx.pop_back();
		maxx.push_back(i);
		if(i>=l){
			while((i-c>=l)&&(query()>s||dp[c]==INF)) c++;
			if(i-c>=l) dp[i]=dp[c]+1;
		}
	}
	cout<<(dp[n]==INF?-1:dp[n]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;


template<typename type>
inline void read(type &x){
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1){
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}


#define INF INT_MAX
deque<int> minn,maxx;
int n,s,l,c;
int a[100005],dp[100005]; 
inline int query(){
	while(!minn.empty()&&minn.front()<c+1) minn.pop_front();
	while(!maxx.empty()&&maxx.front()<c+1) maxx.pop_front();
	return a[maxx.front()]-a[minn.front()];
}
int main(){
	memset(dp,INF,sizeof(dp));
	read(n),read(s),read(l);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	dp[0]=0;
	for(int i=1;i<=n;i++){
		while(!minn.empty()&&a[minn.back()]>=a[i]) minn.pop_back();
		minn.push_back(i);
		while(!maxx.empty()&&a[maxx.back()]<=a[i]) maxx.pop_back();
		maxx.push_back(i);
		if(i>=l){
			while((i-c>=l)&&(query()>s||dp[c]==INF)) c++;
			if(i-c>=l) dp[i]=dp[c]+1;
		}
	}
	cout<<(dp[n]==INF?-1:dp[n]);
	return 0;
}
2024/8/8 10:28
加载中...