上海计算机学会2020年10月月赛C++乙组T2循环逆序对
发布时间
阅读量：
阅读量
题目描述
设有一个长度为n的序列a₁,a₂,…,aₙ以及一个整数k。将该序列a进行k次循环复制操作，则会生成一个新的长度为n×k的循环序列A（亦称周期性序列）。其形式上可表示为：
A = \{ a_1, a_2, \dots, a_n, a_1, a_2, \dots, a_n, \dots \}
其中第m个元素对应于第(m mod n)个元素（m从1开始计）。
- A 的前 n 项等于 a——对于1≤i≤n，有 Ai=ai；
- A 的后 nk−n 项是 a 的循环——对于 n<i≤nk，有 Ai=Ai−n；
请求出 A 中的逆序对数量。逆序对由一组下标 (i,j) 构成，满足 i<j 且 Ai>Aj。
输入格式
第一行：两个整数 n 和 k；
第二行：n 个整数 a1,a2,⋯,an。
输出格式
单个整数：表示 A 中逆序对数量。
数据范围
- 在数据量为20%的情况下，则k值需满足1至10。
- 当数据量达到40%时，则k值应控制在1至5,000之间。
- 则需将k限定于一千万之内。
- 则要求所有样本点数量不超过一百万。
- 其中样本总数n介于一至五千之间，并且每个样本点最多包含五千个特征。
样例数据
输入:
3 2
3 1 4
输出:
5
解析：
循环操作将被应用于该序列k次后，在这种情况下，在每一对序列之间都会引入新的逆序对数量。具体来说，在原始序列中的每个元素i（i=1,2,...,n）将会导致所有后续位置j>i的元素与之形成逆序关系。因此，在每次循环过程中，针对每个元素i而言，只要存在一个位于其前侧且数值较小的元素j（j<i），那么在经过多轮循环后就会产生相应的逆序对数目变化。
在经过K次操作后，在单个序列中出现的逆序对数量也会相应增加。因此需要进一步计算单个序列中存在的逆序对的数量。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int a[500005];
int main() {
long long n, k;
long long ans = 0;
long long d = 0;
long long cnt = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i] > a[j]) {
cnt++;//两个序列间的逆序对个数
if (i < j) {
d++;//单个序列中的逆序对个数
}
}
}
}
//序列内的逆序对d乘以序列个数k再加上序列间的逆序对个数乘以两两成对的序列对数
ans = d * k + cnt * ((k - 1 + 1) * (k - 1) / 2);
cout << ans << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~