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
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
思路：
标程：可以从左往右贪心，问题转化成求一个区间里的mex，由于区间左右端点都是递增的，用个set维护下 即可。
赛时：先对条件进行排序，选择尽量长的条件，放弃被覆盖的条件。然后用一个数组进行标记，表示这个数是否用过，每次往下时要解锁上一个并用循环寻找下一个最小未被标记数进行标记，并且对相交与否进行分类，很明显，结果正确，但TLE了。
标程：
#include
#include
#include
#include
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 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 unused;
for (int i = 1;
i <= n;
++i) {
unused.insert(i);
}
vector 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;
}
【1004.|1004. Distinct Values】赛程：
//B17040312
#include
#include
#include
#include
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.xb.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;
}
