北京大学の大きいデータ機の試験問題

http://bailian.openjudge.cn/dsj2017xly/
次はG題ですが、ちょうど優先キューを試してみます
G:デュアルキュー
合計時間制限:1000 msメモリ制限:65536 kB
説明

  A      。     id      K   ，         P          。         

0        
1 K P      P   K    
2           ，         
3           ，         

入力各行には要求が含まれ、最後の行には停止要求(コード0)が含まれます.顧客リクエスト(コード1)を追加する場合、優先度は一意です.顧客の表示Kは106未満、優先度Pは107未満であり、1人の顧客が複数回追加される可能性があり、毎回の優先度が異なる可能性がある.出力は、要求2および3ごとに、プログラムが1行出力する必要があります.このローには、このリクエストで顧客を見つけたidが含まれます.システムにお客様がいない場合は、0サンプル入力を出力します.

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

サンプル出力

0
20
30
10
0

考え方:
2つの優先キューを使用して、最大スタックと最小スタックをそれぞれ定義しようと考え始めましたが、最上位の要素がポップアップされると、その要素は最小スタックに存在し、これは問題と一致しません.だからタイトルの「ダブルキュー」を使うしかない.次はエラーの2つの優先キューのコードです.本題と一致しませんが、優先キューを定義する方法も記録します.以下のようにします.

#include 
#include 
#include 
#include 
#include 
using namespace std;
struct client{//     ，       ，
    int id;//           ，       
    int pri;
    client(int i, int p){ //    
        id = i;
        pri = p;
    }
    //     ，  <
    bool operator < (const client &a) const{  //     const，    
        if (pri < a.pri) return true;
        else return false;
    }
};
struct client2{  //     ，       ，
    int id;     //           ，       
    int pri;
    client2(int i, int p){
        id = i;
        pri = p;
    }
    bool operator < (const client2 &a) const{
        if (pri < a.pri) return false;
        else return true;
    }
};
int main(){
    //      ，            ，  
    //    2，         ，              
    //         
    priority_queue maxx;  //       
    priority_queue minn; //       
    int p, k, quest;
    while (true){
        cin >> quest;
        if (quest == 0) break;
        if (quest == 1) {
            cin >> k >> p;
            client c(k, p);
            client2 d(k, p);
            minn.push(d);
            maxx.push(c);
        }
        if (quest == 2){  //     
            if (maxx.empty()) cout << "0" << endl;
            else {
                cout << maxx.top().id << endl;
                maxx.pop();
            }
        }
        if (quest == 3){  //     
            if (minn.empty()) cout << "0" << endl;
            else {
                cout << minn.top().id << endl;
                minn.pop();
            }
        }

    }
    return 0;
}

D:特殊暗号ロック総時間制限:1000 msメモリ制限:1024 kBには、n個の接続されたボタンからなる特殊なバイナリ暗号ロックが記述されており(n<30)、ボタンには凹/凸の2つの状態があり、手でボタンを押すとその状態が変化する.
しかし、困ったことに、1つのボタンを押すと、隣接する2つのボタンの状態も逆転します.もちろん、一番左または一番右のボタンを押すと、そのボタンは隣接するボタンにのみ影響します.
現在、パスワードロックのステータスは既知であり、パスワードロックを所望のターゲットステータスに変更するには、少なくとも何回ボタンを押す必要があります.
0、1からなる2つの等長文字列を入力し、現在/ターゲットのパスワードロック状態を表します.0は凹、1は凸を表します.少なくとも必要な押しボタン操作回数を出力し、遷移が実現しない場合はimpossibleを出力する.サンプル入力011 000サンプル出力1
考え方:
この問題は、最初はnが30なので、直接深さ優先で検索しても、タイムアウトしないはずだと思っていましたが、他の人の問題解を見てみると、もともと直接欲張りアルゴリズムでいいことに気づきました.1番目の位置から、異なる場合は2番目のボタンを押して、n個の要素の問題をn-1個に変換し、順次このようにします.(次のコードはまだコンパイルされていません)

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include "stdio.h"
using namespace std;
int main() {
    char a1[30];
    char a2[30];
    int i = 0;
    while (true) {
        scanf("%c", &a1[i++]);
        if (a1[i - 1] == '
') break;
    }
    int j = 0; 
    while (true) {
        scanf("%c", &a2[j++]);
        if (a2[j - 1] == '
') break;
    }
    int ans = 0;
    for (int k = 0; k < i; k++) {
        if (k == i - 1) {
            if (a1[k] != a2[k])  cout << "impossible" << endl;
            else cout << ans << endl;
        }
        if (a1[k] == a2[k]) continue;
        else {
            a1[k + 1] ^= 1;  //    a1[k+1] = 1 - a1[k+1]
            a1[k] ^= 1;
            a1[k + 2] ^= 1;
            ans++;
        }
    }


}