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

chenyizhen · 2025-07-09 19:28:52 · 题解

题目：

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

思路：

形式化题意就是：在数组左右两端挑选最长的不下降子序列，序列的长度即为我们所要求的 ans（即最多付费顾客个数，我开始为资本做局了？）。

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

实现：

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

Code：

#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 效率较低，在这道题中处理时间的差别也很明显。我目前还是最优解呢。