题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6301
多校contest1
题目大意是有一个长度为N的数组,给出M个"事实",每个事实指明一段区间内数字各异,求最后字典序最小的数组。
贪心+构造,给所有"事实"按 边界(左边界优先)排序,然后扫一遍"事实",用一个队列保证用以构造的所有数字最小且区间内各异。
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define scd second
typedef pair<int ,int > pii; vector< pii > facts;
queue< int > num;
bool inq[+];
int ans[+]; int main(){
int Test;
scanf("%d",&Test);
while(Test--){
int N,M;
scanf("%d%d",&N,&M);
memset(inq,false,sizeof(inq));
while(!num.empty()) num.pop();
facts.clear();
for(int i=;i<=N;++i) ans[i]=;
for(int i=;i<M;++i){
pii tmp;
scanf("%d%d",&tmp.fst,&tmp.scd);
if(tmp.fst!=tmp.scd) facts.push_back(tmp);
}
sort(facts.begin(),facts.end());
int lastr=-,lastl=-;
for(int i=;i<facts.size();++i){
int l=facts[i].fst,r=facts[i].scd;
if(r<=lastr) continue;
if(l>lastr){
while(!num.empty()) {
inq[num.front()]=false;
num.pop();
}
int cnt=;
for(int i=l;i<=r;++i){
int flag=;
while(!flag){
if(!inq[cnt]){
inq[cnt]=true;
num.push(cnt);
ans[i]=cnt;
flag=;
}
cnt++;
}
}
lastr=r;
lastl=l;
continue;
}
if(l<=lastr){
for(int i=;i<l-lastl;++i) {
inq[num.front()]=false;
num.pop();
}
int cnt=;
for(int i=lastr+;i<=r;++i){
int flag=;
while(!flag){
if(!inq[cnt]){
inq[cnt]=true;
num.push(cnt);
ans[i]=cnt;
flag=;
}
cnt++;
}
}
lastl=l;
lastr=r;
continue;
}
}
for(int i=;i<=N;++i) printf("%d%c",ans[i],i==N?'\n':' ');
}
return ;
}