2018 Multi-University Training Contest 1 - D Distinct Values (STL+双指针)

题意：数量为N的序列，给定M个区间，要求对每个区间Li，Ri，都有al..r (l≤i<j≤r), ai≠aj。构造这个序列使其字典序最小。

分析：如果对于每个所给区间都暴力扫一遍，1e5的数据量肯定会TLE。其实有一些区间被其他区间完全覆盖，那么在处理其他区间的过程中，该区间已经被处理过了。用一个指针R记录当前已经处理到的位置，用一个数组ends[i]记录以点i为左端点的区间，最其最右端的位置；不作为某个区间左端点的位置，其右端点就是自己。对于每次处理，指针R只会不断增加，不会回退。

还有一个问题就是：如果维护能够使用的数值。如果遇到两个区间有重叠的部分，那么回溯地去找能够使用的数值肯定是会超时的。可以将目前能够使用的数值保存在一个set中，并用一个L指针记录的是上一个处理过的区间的起始位置，那么结果数组中[L，i-1]内的数值，其实是可以重复使用的，将其重新加入集合中。

官方代码：

#include <cstdio>

#include <vector>

#include <algorithm>

#include <set>

#include <iostream>

using namespace std;

#define LOCAL

int main() {

  int T;

  #ifdef LOCAL

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

  #endif

  scanf("%d", &T);

  for (int cas = ; cas <= T; ++cas) {

    int n, m;

    scanf("%d%d", &n, &m);

    vector<int> ends(n,-);

    for (int i = ; i < n; ++i) ends[i] = i;

    for (int i = ; i < m; ++i) {

      int l, r;

      scanf("%d%d", &l, &r);

      ends[l - ] = max(ends[l - ], r - );            //维护每个点需要处理到的最右的位置

    }

    set<int> unused;

    for (int i = ; i <= n; ++i)  unused.insert(i);     //一开始1-N的值都是可以使用的

    vector<int> ret(n);

    int l = , r = -;                  //指针L和指针R

    for (int i = ; 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 = ; i < n-; ++i)   printf("%d ", ret[i]);

    printf("%d\n",ret[n-]);

  }

  return ;

}

巴特西

2018 Multi-University Training Contest 1 - D Distinct Values (STL+双指针)

最新文章

热门文章