[BZOJ入門OJ2092][Noip模拟題]舞會

2092: [Noip模拟題]舞會

Time Limit: 20 Sec  Memory Limit: 256 MB Submit: 9  Solved: 5 [Submit][Status][Web Board]

Description

學校舉行舞會啦,一共有N個人參加，所有人站成一排，從左開始編号，最左邊的人編号為1 ，最右邊的為N。每個人跳舞的熟練度我們用一個整數表示，第i個人的熟練度為Ai，每次熟 練度最接近的一對相鄰男女會出列跳舞，如果有多對那麼最左邊的那一對會先出列，請你給 出出列跳舞的順序。 輸入格式： 第一行一個整數N，第二行N個字元表示N個人的性别，'1'表示男孩，'0'表示女孩。第三行N 個整數表示每人熟練度。

Input

第一行一個整數N，第二行N個字元表示N個人的性别，'1'表示男孩，'0'表示女孩。第三行N 個整數表示每人熟練度。 N<=200000.Ai<=10^7.

Output

第一行一個整數k，表示一共出列k對人。 下面k行，第i行兩個整數ai,bi（ai<bi）,表示第i次出列的是編号為ai，bi的一對。

Sample Input

4
1011
1 1 2 3      

Sample Output

1
1 2      

HINT

Sol

Source

并查集+堆

先把相鄰男女加入堆中，形式為三元組$(i,j,val)$，表示編号為$i$和$j$的人，相差為$val$

這是一個以$val$為關鍵值的小根堆

每次不停地彈，直到彈到兩人都沒跳過

然後删除這兩個人，這兩個人删了之後會有兩邊的人相鄰，判斷是否為男女，是則加入堆

至于左右的人用雙向連結清單維護即可，又想騙我寫并查集

#include <queue>
#include <cstdio>
using namespace std;
char buf[10000000], *ptr = buf - 1;
inline int readint(){
    int f = 1, n = 0;
    char ch = *++ptr;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = *++ptr;
    }
    while(ch <= '9' && ch >= '0'){
        n = (n << 1) + (n << 3) + ch - '0';
        ch = *++ptr;
    }
    return f * n;
}
const int maxn = 200000 + 10;
int N, l[maxn], r[maxn], type[maxn], val[maxn];
bool out[maxn] = {false};
struct Node{
    int a, b, v;
    Node(){}
    Node(int _a, int _b, int _v): a(_a), b(_b), v(_v){}
}t;
class cmp{
    public:
        bool operator () (const Node &x, const Node &y){
            return x.v == y.v ? x.a > y.a : x.v > y.v;
        }
};
inline int abs_(int a){
    return a >= 0 ? a : -a;
}
priority_queue<Node, vector<Node>, cmp> q;
int cnt = 0, ansa[maxn], ansb[maxn];
int main(){
    fread(buf, sizeof(char), sizeof(buf), stdin);
    N = readint();
    char tmp;
    for(int i = 1; i <= N; i++){
        tmp = *++ptr;
        while(tmp < '0' || tmp > '9') tmp = *++ptr;
        type[i] = tmp - '0';
        l[i] = i - 1;
        r[i] = i + 1;
    }
    for(int i = 1; i <= N; i++)
        val[i] = readint();
    for(int i = 1; i < N; i++)
        if(type[i] != type[i + 1])
            q.push(Node(i, i + 1, abs_(val[i] - val[i + 1])));
    while(!q.empty()){
        t = q.top(); q.pop();
        if(out[t.a] || out[t.b]) continue;
        out[t.a] = out[t.b] = true;
        cnt++;
        ansa[cnt] = t.a;
        ansb[cnt] = t.b;
        int lx = l[t.a], rx = r[t.b];
        r[lx] = rx;
        l[rx] = lx;
        if(lx != 0 && rx != N + 1 && type[lx] != type[rx]) q.push(Node(lx, rx, abs_(val[lx] - val[rx])));
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i++)
        printf("%d %d\n", ansa[i], ansb[i]);
    return 0;
}      

轉載于:https://www.cnblogs.com/ruoruoruo/p/7563490.html