codeforces 828 C. String Reconstruction（思维+优先队列）

题目链接：http://codeforces.com/contest/828/problem/C

题解：有点意思的题目，可用优先队列解决一下具体看代码理解。或者用并查集或者用线段树都行。

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#include <cstdio>

#include <map>

#include <string>

#include <vector>

using namespace std;

const int M = 2e6 + 10;

const int N = 1e5 + 10;

int pos;

struct TnT {

    int sta, ed , num;

    TnT() {}

    TnT(int sta , int ed , int num):sta(sta), ed(ed), num(num) {}

    bool operator <(const TnT &a) const {

        return ed - pos > a.ed - pos;

    }

};

priority_queue<TnT>q;

vector<int>vc[M];

string s[N];

int main() {

    int n, k, pp;

    scanf("%d" , &n);

    int Max = 1;

    for(int i = 1 ; i <= n ; i++) {

        cin >> s[i];

        cin >> k;

        int len = s[i].size();

        for(int j = 0 ; j < k ; j++) {

            cin >> pp;

            Max = max(Max , pp + len - 1);

            vc[pp - 1].push_back(i);

        }

    }

    for(pos = 0 ; pos < Max ; pos++) {

        int len = vc[pos].size();

        for(int i = 0 ; i < len ; i++) {

            int L = s[vc[pos][i]].size();

            q.push(TnT(pos , pos + L - 1 , vc[pos][i]));

        }

        if(q.empty()) cout << 'a';

        else {

            cout << s[q.top().num][pos - q.top().sta];

            while(!q.empty()) {

                if(q.top().ed == pos) q.pop();

                else break;

            }

        }

    }

    cout << endl;

    return 0;

}