pass
我们直观上就希望 ai 和 bi 尽可能相似. 我们做出一个大胆的猜想, 是不是 a 序列中排名第 i 的, 和 b 序列中排名第 i 的放在一个位置是最优的呢. 多试几组数据发现是这样的
题目中让我们求交换次数. 而我们现在也只关心相对排名, 所以原先的数值不重要了. 我们把原先的两个序列离散化一下, 都变成 1-n.
那现在就变成了求, 两个 1-n 的数列, 需要交换多少次, 才能变成一样的序列. 又有一个看起来很对的结论, 我们把一个序列保持不动, 让另外一个序列向其靠拢, 和两个一起变换, 在最优情况策略下, 次数是一样的.
那把一个序列变成另外一个序列, 最优需要交换几次呢? 我们联想到逆序对, 是假设有 x 个逆序对, 我们只要交换 x 次, 就能把一个序列变成有序. 那么我们如果把另外一个序列当有有序的标准, 去求另一个序列的逆序对不就是答案么.
用归并排序, 在以一个序列为标准的情况下, 做逆序对是不方便的. 我们有另一种求逆序对的方法, 树状数组求逆序对. 从前往后扫描序列, 当前为 x, 看树状数组中,[x,maxn] 有多少个数. 然后把 x 的位置 + 1. 那这个题也是一样的, 只不过外面嵌套一个 loc[] 而已, 从而用另一个序列的标准去求逆序对. 因为树状数组的原因, 要颠倒一下.
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int MAXN = 110000,mo = 99999997;
- int n,a[MAXN],b[MAXN],tp[MAXN],loc[MAXN],tre[MAXN],ans;
- int lowbit(int x)
- {
- return x & -x;
- }
- int query(int x)
- {
- int res = 0;
- for(;x;x -= lowbit(x))
- {
- res += tre[x];
- res %= mo;
- }
- return res;
- }
- void add(int x)
- {
- for(;x <= n;x += lowbit(x))
- tre[x]++;
- }
- int main()
- {
- scanf("%d",&n);
- for (int i = 1;i <= n;i++)
- {
- scanf("%d",&a[i]);
- tp[i] = a[i];
- }
- sort(tp + 1,tp + n + 1);
- for (int i = 1;i <= n;i++)
- a[i] = lower_bound(tp + 1,tp + n + 1,a[i]) - tp;
- for (int i = 1;i <= n;i++)
- {
- scanf("%d",&b[i]);
- tp[i] = b[i];
- }
- sort(tp + 1,tp + n + 1);
- for (int i = 1;i <= n;i++)
- {
- b[i] = lower_bound(tp + 1,tp + n + 1,b[i]) - tp;
- loc[b[i]] = i;
- }
- for (int i = 1;i <= n;i++)
- {
- ans += query(n - loc[a[i]] + 1);
- ans %= mo;
- add(n - loc[a[i]] + 1);
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3198080.html