SPOJ COWPIC(逆序对变形题)
2024-08-31 07:58:41
SPOJ COWPIC
题意:一个序列,相邻能够交换。问最少交换几次使得变成循环的1-n的当中一种
思路:对于原来正常的变换成1-n而言,答案就是逆序对了,而多了这么一个变形,事实上仅仅须要考虑一下。先求出变换成1-n的逆序对,然后假设原序列变成2, 3, 4 ... n, 1的话。等于是在原来的序列上,把每一个数字模1加n之后求逆序对,那么对于这个新序列而言,仅仅有原来最大的n变成了1会受影响,那么最大的n原来的逆序对就不在是逆序对,原来不是逆序对的就变成逆序对了,所以仅仅要一開始记录下每一个数字的位置,然后在循环一遍,求出相应每一个数字+1变成1之后,会添加降低的逆序对统计出来,不断维护最小值就可以
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 100005;
typedef long long ll; #define lowbit(x) (x&(-x)) int bit[N]; void add(int x, int v) {
while (x < N) {
bit[x] += v;
x += lowbit(x);
}
} int get(int x) {
int ans = 0;
while (x) {
ans += bit[x];
x -= lowbit(x);
}
return ans;
} int n, c[N], pos[N]; int main() {
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
pos[c[i]] = i;
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += i - 1 - get(c[i]);
add(c[i], 1);
}
ll ans2 = ans;
for (int i = 1; i <= n; i++) {
ans2 -= pos[i] - 1;
ans2 += n - pos[i];
ans = min(ans, ans2);
}
printf("%lld\n", ans);
}
return 0;
}
最新文章
- linux——ssh服务
- Ubuntu下无法安装sun-java6-jdk的解决办法
- java如何连接testlink
- HDU 5950:Recursive sequence(矩阵快速幂)
- struts2中form提交到action中的中文参数乱码问题解决办法(包括取中文路径)
- WPF Canvas 画区域
- Tomcat的错误 之 java.lang.IllegalArgumentException: Document base * does not exist
- 自定义ORM框架(转转)
- WinCE 5.0模拟器,在 win7 下安装后, VS2008里不显示
- POJ	2062 HDU 1528 ZOJ 2223 Card Game Cheater
- 二、IPC机制
- Rsync使用方法
- webdirver.Chrom() selenium webdirver调用谷歌浏览器的问题解决
- Mongodb Mysql NoSQL的区别和联系
- open还是codecs.open区别
- C++:MSVCRTD.lib(crtexe.obj) : error LNK2019: 无法解析的外部符号 _main,该符号在函数 ___tmainCRTStart
- Cocos Creator iPhoneX适配的解决办法
- FineBI学习系列之FineBI的Windows里安装步骤(图文详解)
- 洛咕 P4491 [HAOI2018]染色
- linux-RPM 打包原理 SPEC 编写规范