題目鏈接在此
題意是給定一個(gè)長度n, 再給一個(gè)[0,n-1]的排列, 可以循環(huán)地將第一個(gè)數(shù)放置序列末尾, 問這樣循環(huán)出來的所有序列中, 最小的逆序數(shù)是多少?
思路:
- 先求得原序列串的逆序數(shù)
- 對(duì)于在當(dāng)前序列串的第一個(gè)數(shù)字來說,貢獻(xiàn)的逆序數(shù)是第一位后小于自己的數(shù)的數(shù)量即 a[1] - 1
- 將第一個(gè)數(shù)字放到末端, 原先在第一位貢獻(xiàn)逆序數(shù)量被消除,在末尾貢獻(xiàn)的逆序數(shù)是在末位前大于自己的數(shù)的數(shù)量, 即 n - a[1]
舉個(gè)莉子, 序列3 1 4 5 2中, 3貢獻(xiàn)的逆序數(shù)自然是3 - 1 = 2個(gè)(小于自己又在后面(必然在自己后面)的)
3若到末位, 成1 4 5 2 3, 貢獻(xiàn)的則是5 - 3 = 2個(gè)(大于自己的又在前面(必然在自己前面)的)
綜上所述, 每次循環(huán)施逾，相當(dāng)于當(dāng)前原序列的總逆序數(shù), 設(shè)為cur, 減去消失的逆序數(shù) + 新添加的,得
cur = cur - (a[1] - 1) + (n - a[1])
至于如何求得原序列的逆序數(shù),方法很多,常用的有歸并排序/線段樹/這里使用的樹狀數(shù)組
注意, 如果是樹狀數(shù)組,由于編號(hào)是[1,n] 所以對(duì)于a[i],值域也得是[1,n] 題目是[0,n-1]盒蟆，所以讀取后得++a[i]調(diào)一下
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxN = 5005, inf = 0x3f3f3f3f;
int A[maxN], bit[maxN + 1], N;
void add(int i, int x) { while (i <= N) { bit[i] += x; i += i & -i; } }
int sum(int i) { int ret = 0; while (i) { ret += bit[i]; i -= i & -i; } return ret; }
int main() {
// freopen("data.in", "r", stdin);
while (~scanf("%d", &N) && N) {
memset(bit, 0, sizeof(bit));
int inv = 0;
for (int i = 0; i < N; ++i) {
scanf("%d", &A[i]);
++A[i];
inv += i - sum(A[i]);
add(A[i], 1);
}
int ans = inv, u, v;
for (int i = 0; i < N; ++i) {
u = A[i] - 1;
v = N - A[i];
inv = inv - u + v;
ans = min(ans, inv);
}
printf("%d\n", ans);
}
return 0;
}
附加：
到最后..還是想稍微整理一下,為什么樹狀數(shù)組能求逆序數(shù)?
首先可能得先了解一下什么是樹狀數(shù)組,長什么樣,節(jié)點(diǎn)怎么和數(shù)組下標(biāo)對(duì)應(yīng)起來,這個(gè)這里就不打算說了..樹狀數(shù)組的一般操作:
給定i, 計(jì)算a1 + a2 + a3 + ... an
給定i和x, 執(zhí)行 ai += x
在知道這個(gè)數(shù)據(jù)結(jié)構(gòu)的前提下:
求某個(gè)逆序數(shù),即求在自己前面又大于自己的數(shù)量,那我們只需要：
在當(dāng)前數(shù)字下標(biāo)是j, 值是a[j], 在數(shù)組里做個(gè)小標(biāo)記,比如 bit[a[j]] += 1, 假設(shè)所有數(shù)都這樣處理過,那以后我們要統(tǒng)計(jì)當(dāng)前數(shù)字下有多少個(gè)小于自己的數(shù)字呢? 求個(gè)前n項(xiàng)和就可以了, 那大于自己的數(shù)字呢珊皿？自然就是n - sum(a[j])啦..把每個(gè)數(shù)字的逆序數(shù)一加,得解
到這兒..其實(shí)思想可以再簡(jiǎn)單化一些: 你就想象你有一個(gè)標(biāo)記數(shù)組vis[maxN] = {0} ,每當(dāng)一個(gè)數(shù)字a[j], 出現(xiàn)了就vis[a[j]] = 1, 那你要統(tǒng)計(jì)前面有多少個(gè)小于自己的數(shù)字,相當(dāng)于統(tǒng)計(jì)j前面出現(xiàn)了多少個(gè)1(求前n項(xiàng)和)独令，設(shè)為sum,那么n - sum腌闯，就是當(dāng)前數(shù)字貢獻(xiàn)的逆序數(shù)了。 但是這種方法效率很低,只不過利用了樹狀數(shù)組來加速,思路是一樣的廓脆。
