洛谷P1966 火柴排队(逆序对)
程序员文章站
2022-03-26 09:31:07
题意 "题目链接" Sol 不算很难的一道题 首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置 证明也比较trivial。假设$A$中有两个元素$a, b$,$B$中有两个元素$c, d$ 然后分别讨论一下当$a define lb(x) (x & x) def ......
题意
sol
不算很难的一道题
首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置
证明也比较trivial。假设\(a\)中有两个元素\(a, b\),\(b\)中有两个元素\(c, d\)
然后分别讨论一下当\(a < b\)时\(c\)与\(a\)对应优还是与\(b\)对应优。
化简的时候直接对两个式子做差。
这样我们找到第二个序列中的每个数应该排到哪个位置,树状数组求一下逆序对就行了。
#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; }
上一篇: 简单介绍一下,PHP版本的区别