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

__VN · 2025-06-29 20:16:33 · 题解

P12987 [GCJ 2022 #1B] Pancake Deque

题目传送门 题解代码通过记录

思路

先使队列两端较小值出列，可使美味值最大值增长更缓慢。

这样后续煎饼更容易满足支付条件（只需 \geq 较小值而非较大值），增加后续付费机会。

注意

当一个煎饼的美味值不低于之前所有煎饼的美味值时，该顾客才为其煎饼付费。

完整代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        int n;
        int last=0;         //之前所有顾客获得的煎饼的美味值最大值 
        int sum=0;          //付费顾客数量
        list<int> d;        //煎饼！ 
        cin>>n;
        while(n--){         //输入
            int x;          
            cin>>x;
            d.push_back(x);
        }
        while(!d.empty()){
            if(d.front()>d.back()){                     //判断队首和队尾煎饼的美味值 
                if(d.back()>=last)last=d.back(),sum++;  //判断是否不低于之前所有顾客获得的煎饼的美味值
                d.pop_back();                           //出队 
            }else{                                      //同上 
                if(d.front()>=last)last=d.front(),sum++;
                d.pop_front();
            }
        }
        printf("Case #%d: %d\n",i,sum);
    }
}