队列

基数排序

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

void radix_sort(int a[], int n){
    queue<int> q[10];
    int max = 0;
    for(int i = 0; i < n; i++){
        if(a[i] > a[max]) max = i;
    }
    int t = a[max];
    int l = 0;
    while(t > 0){
        l++;
        t = t / 10;
    }

    for(int i = 0; i < l; i++){
        int p = pow(10, i);
        for(int j = 0; j < n; j++){
            int d = (a[j] / p) % 10;
            q[d].push(a[j]);
        }

        int idx = 0;
        for(int j = 0; j < 10; j++){
            while(!q[j].empty()){
                a[idx++] = q[j].front();
                q[j].pop();
            }
        }
    }


}

int main(){
    int a[10] = {3, 5, 2, 88, 1, 32, 98, 4, 22, 8};
    radix_sort(a, 10);
    for(int i = 0; i < 10; i++){
        cout << a[i] << " ";
    }
    return 0;
}

P2058 [NOIP2016 普及组] 海港

#include<iostream>
#include<queue>
using namespace std;

const int N = 1e5 + 5;
int cnt[N];

struct Person{
    int tm;
    int nat;
};

int main(){
    int n;
    cin >> n;
    queue<Person> q;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        int t, k;
        cin >> t >> k;
        while(k--){
            int nat;
            cin >> nat;
            q.push({t, nat});
            if(cnt[nat] == 0) ans++;
            cnt[nat]++;
        }

        while(t - q.front().tm >= 86400){
            cnt[q.front().nat]--;
            if(cnt[q.front().nat] == 0) ans--;
            q.pop();
        }
        cout << ans << endl;
    }
    return 0;
}