并行排序 Namomo 每日一题div1 04-02

题目链接

题目

题意

给定一个长度为$n$的序列$a$， 如果两个点$i, j$满足$i < j, a_i > a_j$， 那么这两个点之间存在一条边， 对这$n$个点染色， 要求每一条边两个端点的颜色不能相同， 问最少的颜色数量

数据范围

$T$组数据

$1 \leq \sum n \leq 10^6$

题解

我终于也做到原题了！！！

这是我的第一场icpc， 45th昆明的一道题， 当时队友想到了怎么做

思路

如果我们从对于每个数从前面找所有大于它的数然后染色， 显然不现实也不可操作， 所以我们换一种思路， 将已经染好色的数按照颜色分组

我们正序枚举每个$i$， 同时维护每种颜色中最大的的那个数， 计为$mx_j$， 如果$a_i < mx_j$， 那么$a_i$就不能染这种颜色， 如果$a_i$比所有的$mx$都小， 那么就需要重新开一个颜色了

在添加的过程中中$mx$肯定是倒序的， 当我们找到第一个$mx_j \leq a_i$后， 将$mx_j$变为$a_i$就可以了

为什么是第一个？

假设现在$mx$序列是$7, 4, 2$， 我们现在的$a_i = 5$， 我们把它染成$2$代表的颜色， 变成$7, 4, 5$， 这时候来一个$3$， 就要新开一个颜色了， 但是如果是$7, 5, 2$就不会， 所以我们尽量要让每个颜色内的数尽量紧凑， 这样不仅可以保证答案最优， 还能维持降序， 有利于查找

代码

为了直接使用lower_bound， 本代码倒序枚举$i$， 本质与正序枚举相同

#include <iostream>
#include <cstdio>
#include <algorithm>

int t;
int n;
int a[1000006];
int mx[1000006], ans;

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        ans = 1;

        scanf("%d", &n);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

        mx[ans] = a[n];
        for(int i = n - 1; i >= 1; i --)
        {
            int pos = std:: lower_bound(mx + 1, mx + ans + 1, a[i]) - mx;

            if(pos > ans)
                mx[++ ans] = a[i];
            else
                mx[pos] = a[i];
        }

        printf("%d\n", ans);
    }

    return 0;
}