C++基礎題 洛谷 P3613 【深基15. 例2】寄包櫃

map and pair ( stl ) 的搜尋應用。

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    map<pair<int,int>,int> mp;
    int n,q;
    cin>>n>>q;

    for(int i=0;i<q;i++){
        int a;
        cin>>a;

        if(a==1){
            int x,y,st;
            cin>>x>>y>>st;
            mp[{x,y}]=st;
        }else{
            int x,y;
            cin>>x>>y;
            cout<<mp[{x,y}]<<"\n";
        }
    }
    return 0;
}

出處:https://www.luogu.com.cn/problem/P3613

C++基礎題 TIOJ 1911 . 雲端列印

用 priority_queue 與 unordered_map 。

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    priority_queue<int> mx;
    priority_queue<int,vector<int>,greater<int>> mn;
    unordered_map<int,int> s;

    int t;
    while(cin>>t){
        if(t==0) break;

        if(t==-1){
            while(!mn.empty() && !s[mn.top()]){
                mn.pop();
            }
            if(!mn.empty()){    
                cout<<mn.top()<<' ';
                s[mn.top()]--;
                mn.pop();
            }
        }else if(t==-2){
            while(!mx.empty() && !s[mx.top()]){
                mx.pop();
            }
            if(!mx.empty()){
                cout<<mx.top()<<' ';
                s[mx.top()]--;
                mx.pop();
            }
        }else{
            s[t]++;
            mx.push(t);
            mn.push(t);
        }
    }
    return 0;
}

C++ 基礎題 單調對列

單調對列模板,因為題目的關係所以用 1 開始。

#include<bits/stdc++.h>
using namespace std;

int idx[5000100],nm[5000100];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    stack<int> st;
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>nm[i];
        while(!st.empty() && nm[st.top()]<nm[i]){
            idx[st.top()]=i;
            st.pop();
        }

        st.push(i);
    }

    while(!st.empty()){
        idx[st.top()]=0;
        st.pop();
    }

    for(int i=1;i<=n;i++){
        cout<<idx[i]<<" ";
    }
    return 0;
}