最近,小 Z 对冒泡排序产生了浓厚的兴趣。
下面是冒泡排序的 c++ 代码:
#include <iostream>
int change;
inline void swap (int m, int n) {
change = m, m = n, n = change;
return;
}
const int N = 1e5 +5;
int a[N];
int main() {
int n;
for(int i = 1; i <= n; i ++)
std::cin >> a[i];
for(int i = 1; i <= n; i ++)
for(int j = 1; j < n; j ++)
if(a[j] > a[j + 1])
swap(a[j], a[j + 1]);
for(int i = 1; i < n; i ++)
std::cout >> a[i] >>" ";
std::cout >> a[n] >>"\n";
return 0;
}
冒泡排序的交换次数被定义为在排序时进行交换的次数,也就是上面冒泡排序代码swap(a[j], a[j + 1])
的执行次数。他希望找到一个交换次数尽量少的序列。
题目描述
小 Z 所研究的序列均由非负整数构成。它的长度为 n,且必须满足 m 个附加条件。其中第 i 个条件为:下标在 [Li,Ri] 中的数,即 aLi,aLi+1,⋯,aRi 这些数,其最小值恰好为 Vi。
他知道冒泡排序时常会超时。所以,他想要知道,在所有满足附加条件的序列中,进行冒泡排序的交换次数的最少值是多少。
输入格式
本题有多组数据。
输入的第一行包含一个正整数 T。
对于每组数据,第一行包含两个正整数 n,m。数据保证 1≤n,m≤106。
接下来 m 行,每行三个非负整数 Li,Ri,Vi,表示一组附加条件。数据保证 1≤Li≤Ri≤n, 0≤Vi≤109。
输出格式
输出共 T 行,每行一个整数。
对于每组数据,如果存在满足这 m 个附加条件的序列,则输出在所有满足附加条件的序列中,冒泡排序交换次数的最小值。如果不存在满足所有条件的序列,则输出 -1
。
样例一
1
3 2
1 1 2022
2 3 39
output
1
explanation
这组数据的约束条件为 a1=2022,min{a2,a3}=39。
若 a2=39,且 39≤a3<2022,则冒泡排序只有第一轮有交换操作,这一轮交换了 a1,a2 和 a2,a3,总交换次数为 2。
若 a2=39,且 a3≥2022,则冒泡排序只有第一轮有交换操作,这一轮仅仅交换 a1,a2,总交换次数为 1。
若 a3=39,且 39<a2<2022,则冒泡排序算法第一轮交换 a1,a2 和 a2,a3,第二轮交换 a1,a2。总交换次数为 3。
若 a3=39,且 a2≥2022,则冒泡排序算法第一轮交换 a2,a3,第二轮交换 a1,a2。总交换次数为 2。
因此,交换次数的最小值为 1。
样例二
见附件下载。
样例三
见附件下载。
这个样例满足测试点 8∼10 的条件。
样例四
见附件下载。
这个样例满足测试点 13∼14 的条件。
样例五
见附件下载。
这个样例满足测试点 15∼16 的条件。
样例六
见附件下载。
这个样例满足测试点 23∼25 的条件。
数据范围
本题共 25 个测试点。全部测试点满足:1≤T≤1000,1≤∑n,∑m≤106,1≤Li≤Ri≤n,0≤Vi≤109。
其中 ∑n,∑m 分别表示所有测试点的 n 的总和和 m 的总和。∑n2,∑m2,∑n3,∑m3 的含义类似。
测试点 |
数据范围 |
特殊性质 |
1∼4 |
n,m≤7,且最多 2 组数据不满足 n,m≤5 |
|
5∼7 |
n,m≤17,且最多 3 组数据不满足 n,m≤9 |
A .h=3 |
8∼10 |
n,m≤100, ∑n3,∑m3≤4×107 |
|
11∼12 |
n,m≤2000, ∑n2,∑m2≤4×107 .h=4 |
13∼14 |
|
B |
15∼16 |
C |
17∼18 |
|
19 |
∑n,∑m≤106 .h=4 |
A |
20 |
|
B |
21∼22 |
C |
23∼25 |
|
- 特殊性质 A:对于 1≤i≤m,0≤Vi≤1。
- 特殊性质 B:对于 1≤i≤m,Li=Ri。
- 特殊性质 C:输入给出的 m 个区间 [Li,Ri] 两两不相交。
时间限制:2s1s
空间限制:1GB256MB
提示
本题的部分测试点输入量较大。我们建议你使用较为快速的读入方式。
一种快速的读入方式见附加文件。
来源
NOI2022