题解：P12987 [GCJ 2022 #1B] Pancake Deque

题目：

在数组两端选数，使后选的数尽量多的大于等于之前选出的数。

思路：

形式化题意就是：在数组左右两端挑选最长的不下降子序列，序列的长度即为我们所要求的

ans

（即最多付费顾客个数，~~我开始为资本做局了？~~）。

那我们根据贪心的思想就可以想到先选出左右两端小的数，毕竟大的数不会被小的数所覆盖，反之则不然，这样我们就可尽可能多的选出付费顾客个数。

实现：

通过 C++ 自带的双端队列或自己通过数组模拟双端队列来模拟挑选过程。
在挑选过程中记录已挑选的最大值以便于今后的比较。
按照题目输出。

Code：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
int d[N],cnt=0,n,T;
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);	
	read(T);
	while(T--){
		read(n);
		for(int i=1;i<=n;i++) read(d[i]);
		int head=1,tail=n,ans=0,maxn=0;
		while(head<=tail){
			if(d[tail]>d[head]){
				ans+=d[head]>=maxn;
				maxn=max(maxn,d[head]);
				head++;
			}else{
				ans+=d[tail]>=maxn;
				maxn=max(maxn,d[tail]);
				tail--;
			}
		}
		printf("Case #%lld: %lld\n",++cnt,ans);
	}
	return 0;
}

在这里我选用自己模拟双端队列，因为自带的 deque 效率较低，在这道题中处理时间的差别也很明显。~~我目前还是最优解呢。~~

题解：P12987 [GCJ 2022 #1B] Pancake Deque

文章操作

题目：

思路：

实现：

Code：

相关推荐

评论

题解：P12987 [GCJ 2022 #1B] Pancake Deque