題意

題目鏈接

Sol

不算很難的一道題

首先要保證權(quán)值最小，不難想到一種貪心策略，即把兩個(gè)序列中rank相同的數(shù)放到同一個(gè)位置

證明也比較trivial。假設(shè)\(A\)中有兩個(gè)元素\(a, b\)，\(B\)中有兩個(gè)元素\(c, d\)

然后分別討論一下當(dāng)\(a < b\)時(shí)\(c\)與\(a\)對(duì)應(yīng)優(yōu)還是與\(b\)對(duì)應(yīng)優(yōu)。

化簡(jiǎn)的時(shí)候直接對(duì)兩個(gè)式子做差。

這樣我們找到第二個(gè)序列中的每個(gè)數(shù)應(yīng)該排到哪個(gè)位置，樹(shù)狀數(shù)組求一下逆序?qū)托辛恕?/p> #include<bits/stdc++.h> #define lb(x) (x & -x) #define Fin(x) {freopen(#x".in", "r", stdin);} using namespace std; const int MAXN = 1e5 + 10, mod = 99999997; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, a[MAXN], b[MAXN], pos[MAXN], rak[MAXN], date[MAXN], T[MAXN]; void Get(int *a) {memcpy(date, a, sizeof(a) * (N + 1));sort(date + 1, date + N + 1);int num = unique(date + 1, date + N + 1) - date - 1;for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date; } void Add(int x, int val) {while(x <= N) T[x] += val, x += lb(x); } int Query(int pos) {int ans = 0;while(pos) ans += T[pos], pos -= lb(pos);return ans; } int add(int x, int y) {if(x + y < 0) return x + y + mod;else return (x + y >= mod) ? x + y - mod : x + y; } signed main() {N = read();for(int i = 1; i <= N; i++) a[i] = read();for(int i = 1; i <= N; i++) b[i] = read();Get(a); Get(b);for(int i = 1; i <= N; i++) pos[a[i]] = i;for(int i = 1; i <= N; i++) rak[i] = pos[b[i]];int ans = 0;for(int i = 1; i <= N; i++) Add(rak[i], 1), ans = add(ans, i - Query(rak[i]));printf("%d", ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/9835055.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1966 火柴排队(逆序对)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。