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

yyz0526 · 2025-07-13 08:13:56 · 题解

题目大意：

以双端队列（deque 讲解）的方式供应煎饼，每个煎饼有一个美味值，只有当一个煎饼的美味值不低于之前所有顾客获得的煎饼的美味值时，该顾客才需要为其煎饼付费。求最大化付费顾客的数量。

思路：

想要最大化付费顾客数量，每一次取的煎饼的美味值就需要最小，取队首和队尾的最小值，然后与前几次选择的煎饼的最大美味值进行比较，如果不小于，那么就要付费。

代码：

#include<bits/stdc++.h>
using namespace std;
deque<int> d;
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        while(!d.empty()){ // 清空队列。
            d.pop_back();
        }
        int n,sum=0;
        int maxx=0; // 当前最大美味值。
        scanf("%d",&n);
        for(int j=0;j<n;j++){
            int x;
            scanf("%d",&x);
            d.push_back(x);
        }
        while(!d.empty()){
            int f=d.front();
            int b=d.back();
            if(f<b){ // 队首小。
                if(maxx<=f){
                    maxx=f;
                    sum++;
                }
                d.pop_front();
            }
            else{ // 队尾小。
                if(maxx<=b){
                    maxx=b;
                    sum++;
                }
                d.pop_back();
            }
        }
        printf("Case #%d: %d\n",i,sum);
    }
    return 0;
}