杭电多校第一场1004 Distinct Values

1004 Distinct Values

题意

构造一个字典序最小的数组，其中m个区间中的数不能相同

做法

考虑每一个位置当前能放的数中的最小数，所以我们需要记录从 当前要放的位置 到 往前多少是这个不能重复的区间的边界，不能和这个区间里面的重复
所以用pre数组记录最远，然后之前pre[i] 之前的数就能继续用了加入到set或者优先队列里，每次取最小
这个需要画图，我画工不好，就不献丑了，可以看看代码，有助于理解

参考代码

dls（杜老师讲题解的时候是用set实现的，优先队列大概快200ms的样子）
1 优先队列实现

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double PI = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e5+100;
int pre[maxn];
int a[maxn],b[maxn];
int ans[maxn];
int main(void)
{
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
// freopen("out.txt","r")
   int T;
   cin>>T;
   while(T--){
         int n,m; 
         scanf("%d %d",&n,&m);
         for(int i = 1;i <= n; ++i)
             pre[i] = i;
         for(int i = 1;i <= m; ++i)
          scanf("%d %d",&a[i],&b[i]),pre[b[i]] = min( a[i],pre[b[i]]);//取最远
       
         for(int i = n-1;i >= 1; --i)
          pre[i] = min(pre[i],pre[i+1]);// 取最远的不能重复的区间
         priority_queue<int,vector<int>,greater<int>> q;
         for(int i = 1;i <= n;++i)
          q.push(i);// 一开始1.. n都是能放的

         int p = 1;
         for(int i = 1;i <= n;++i){
              for(;p < pre[i];++p)
                 q.push(ans[p]);// 将之前放过的数回收
               int t = q.top();q.pop();// 放下最小数
               ans[i] = t;
             
         }
      for(int i = 1;i <= n ;++i)
         printf("%d%c",ans[i],i==n?'\n':' ');
         
   }
   return 0;
}

2 set实现

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double PI = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e5+100;
int pre[maxn];
int a[maxn],b[maxn];
int ans[maxn];
int main(void)
{
//    freopen("in.txt","r",stdin);
//    freopen("out1.txt","w",stdout);
//    freopen("out.txt","r")
   int T;
   cin>>T;
   while(T--){
         int n,m; 
         scanf("%d %d",&n,&m);
         for(int i = 1;i <= n; ++i)
             pre[i] = i;
         for(int i = 1;i <= m; ++i)
          scanf("%d %d",&a[i],&b[i]),pre[b[i]] = min( a[i],pre[b[i]]);
       
         for(int i = n-1;i >= 1; --i)
          pre[i] = min(pre[i],pre[i+1]);
         set<int> q;
         for(int i = 1;i <= n;++i)
          q.insert(i);
         //         cout<<"........."<<endl; 
//         for(int i = 1; i <= n; ++i)
//           cout<<pre[i]<<" ";
//            cout<<"....."<<endl;
         int p = 1;
         for(int i = 1;i <= n;++i){
              for(;p < pre[i];++p)
                 q.insert(ans[p]);
               int t = *q.begin();q.erase(t);
               ans[i] = t;
             
         }
      for(int i = 1;i <= n ;++i)
         printf("%d%c",ans[i],i==n?'\n':' ');
         
   }
  
  
  

   return 0;
}