欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 多校赛 Distinct Values

程序员文章站 2022-06-09 19:02:47
...

【题目链接】

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

hdu 多校赛 Distinct Values

#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' : ' ');
    }
}