1004. Distinct Values

1004. Distinct Values

• Time limit: 2 seconds
• Memory limit: 32 megabytes
  Problem Description
  Chiaki has an array of n positive integers. You are told some facts about the array: for every two elements ai and aj in the subarray al..r (l≤i<j≤r), ai≠ ajholds. 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≤n,m≤105) -- the length of the array and the number of facts. Each of the next m lines contains two integers liand ri (1≤li≤ri≤n). It is guaranteed that neither the sum of all n nor the sum of all m exceeds 106.
  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
  3 2 1 1 2 4 2 1 2 3 4 5 2 1 3 2 4
  Sample Output
  1 2 1 2 1 2 1 2 3 1 1

题意：给出n，m；n代表右一个由n个1到n的数组成的数组，m表示m个限制条件，每个限制条件由两个数组成，在这两个数的区间内所有的数不重复，求字母序最小的满足所有限制条件的数组。
思路：
标程：可以从左往右贪心，问题转化成求一个区间里的mex，由于区间左右端点都是递增的，用个set维护下 即可。
赛时：先对条件进行排序，选择尽量长的条件，放弃被覆盖的条件。然后用一个数组进行标记，表示这个数是否用过，每次往下时要解锁上一个并用循环寻找下一个最小未被标记数进行标记，并且对相交与否进行分类，很明显，结果正确，但TLE了。

标程：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
int main() {
  int T;
  scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> ends(n, -1);
    for (int i = 0; i < n; ++i) ends[i] = i;
    for (int i = 0; i < m; ++i) {
      int l, r;
      scanf("%d%d", &l, &r);
      ends[l - 1] = max(ends[l - 1], r - 1);
    }
    set<int> unused;
    for (int i = 1; i <= n; ++i) {
      unused.insert(i);
    }
    vector<int> ret(n);
    int l = 0, r = -1;
    for (int i = 0; i < n; ++i) {
      if (r >= ends[i]) continue;
      while (l < i) {
        unused.insert(ret[l++]);
      }
      while (r < ends[i]) {
        ret[++r] = *unused.begin();
        unused.erase(ret[r]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i) putchar(' ');
      printf("%d", ret[i]);
    }
    puts("");
  }
  return 0;
}

赛程：

//B17040312
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;


    int pos1[100005];
    int pos2[100005];
    int slove[100005];
    struct point{
        int x;
        int y;
    }p[100005];

    bool cmp(const point &a , const point &b){
        if(a.x<b.x) return true;
        else if(a.x>b.x) return false;
        else{
            return a.y>b.y;
        }
    }


int main(){
    int t,n,m;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n ,&m);
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &p[i].x,&p[i].y);
        }
    
        for(int i = 1; i <= n; i++){
            slove[i] = 1;
            pos1[i] = 1;
            pos2[i] = 1;
        }
        sort(p+1, p+m+1,cmp);
        for(int i = 1; i <= m; i++){
            if(pos1[p[i].x]==0&&pos1[p[i].y]==0) continue;
            else if(pos1[p[i].x]==0&&pos1[p[i].y]!=0){
                for(int j = p[i-1].x; j < p[i].x; j++){
                    pos2[slove[j]] = 1;
                }
                for(int j = p[i-1].y+1; j <= p[i].y; j++){
                    pos1[j] = 0;
                    for(int q = 1; q <= n; q++){
                        if(pos2[q] == 1){
                            slove[j] = q;
                            pos2[q] = 0;
                            break;
                        }
                    }
                }
            
            }else{
                if(i != 1){
                    for(int j = p[i-1].x; j <= p[i-1].y; j++){
                        pos2[slove[j]] = 1;
                    }
                }
                int h = 1;
                for(int j = p[i].x; j <= p[i].y; j++){
                    slove[j] = h++;
                    pos2[h-1] = 0;
                    pos1[j] = 0;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            printf("%d", slove[i]);
            if(i == n) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}