Distinct Values（单调性+贪心+优先队列)

Description:

Chiaki has an array of $n$ positive integers. You are told some facts about the array: for every two elements $a_{i}$ and $a_{j}$ in the subarray $a_{l . . r}$ ( $l \leq i < j \leq r$ ), $a_{i} \neq a_{j}$ holds.
Chiaki would like to find a lexicographically minimal array which meets the facts.

Input:

There are multiple test cases. The first line of input contains an integer $T$ , indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 10^{5}$ ) — the length of the array and the number of facts. Each of the next $m$ lines contains two integers $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ ).

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $10^{6}$ .

Output:

For each test case, output $n$ integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

Sample Input:

Sample Output:

1 2
1 2 1 2
1 2 3 1 1

题意：
- 给出m个区间，区间内的数不重复，使得得出的序列字典序最小
题解：
- 记录每个r能影响的最左的l为pre[r]，用优先队列存储当前能放的数，用vis表示位置，每次可以回收vis到pre[r]的数进优先队列，更新vis
- 但是这样有个问题，就是更小的r的pre[r]不能大于更大的r的pre[r]，否则会重复回收，所以按照贪心的思想，我们让pre[i]=min(pre[i-1],pre[i])

代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
//#define CLR(a) memset(a,sizeof(a),0)

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;

const int maxn=1e6+10;
int t,n,m;

int pre[maxn];
int l[maxn];
int r[maxn];
int out[maxn];
int main(){
    //ifstream in;
        //ofstream out;
    //in.open("in.txt");
    scanf("%d", &t);
   // in>>t;
    while(t--){
        //in>>n>>m;
        scanf("%d%d", &n,&m);
        rep(i,1,n)pre[i]=i;
        rep(i,1,m){
            scanf("%d%d", &l[i],&r[i]);
            //in>>l[i]>>r[i];
            pre[r[i]]=min(l[i],pre[r[i]]);
        }

        priority_queue<int,vector<int>, greater<int> >q;
        q.push(n);
        per(i,1,n-1){
            pre[i]=min(pre[i],pre[i+1]);
            q.push(i);
//            cout<<pre[i]<<endl;
        }
        int vis=1;
        rep(i,1,n){
            //rep(vis,1,pre[i]-1)
            while(vis<pre[i]){
                q.push(out[vis]);
                ++vis;
            }
            int t = q.top();
            q.pop();
            out[i]=t;
        }
        rep(i,1,n){
            printf("%d",out[i]);
            if(i!=n)printf(" ");
            else puts("");
        }
    }

    return 0;
}

Description:

Input:

Output:

Sample Input:

Sample Output:

发表评论 取消回复

发表评论取消回复