Zth's Blog

记录学习路上的点滴

0%

并行排序 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$, 本质与正序枚举相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}