hdu 多校赛 Distinct Values
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
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
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 li and 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
Source
2018 Multi-University Training Contest 1
先初始化
set,que,ans数组
,然后对m组数据预处理que[a] = max(que[a], b)
。
当遍历到i
时,set里面存的是ans[i]之后没有出现的数字,所以在每次i++
后,都要将ans[i-1]重新放入到ans数组中,
当遍历到i
时,最少应该输出que[i]
个数字,若此时输出的数字小于que[i]
,则从set从取出que[i]-i
个元素放入ans数组中,反之,不进行任何操作。
下面给一组案例
1
5 2
1 3
2 4
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m, a, b;
scanf("%d%d", &n, &m);
int que[100005];
for (int i = 1; i <= n; i++)
que[i] = i;
for (int i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
que[a] = max(que[a], b);
}
int ans[100005];
set<int>s;
for (int i = 1; i <= n; i++)
s.insert(i);
int output = 1, input = 1;
for (int i = 1; i <= n; i++)
{
if (i != 1)
s.insert(ans[i - 1]);
while (output <= que[i])
{
ans[output] = *s.begin();
s.erase(ans[output++]);
}
}
for (int i = 1; i <= n; i++)
printf("%d%c", ans[i], i == n ? '\n' : ' ');
}
}
上一篇: 单片机开发 --- 定时器中断
下一篇: Spring中自定义拦截器的使用
推荐阅读
-
HDU6312 Game (多校第二场1004) 简单博弈
-
HDU多校四
-
2020hdu多校10
-
HDU6299 Balanced Sequence (多校第一场1002) (贪心)
-
[斐波那契幂和+二次剩余]2020hdu多校 6755 Fibonacci Sum
-
[HDU多校2020]第三场 1004 Tokitsukaze and Multiple (贪心/dp)
-
hdu6336 多校第四场E题 Matrix from Arrays
-
杭电多校04补题 HDU6336 Problem E. Matrix from Arrays【构造】
-
2020杭电多校集训-Distinct Sub-palindromes
-
HDU6301 Distinct Values (多校第一场1004) (贪心)