首页 > 代码库 > SPOJ COWPIC(逆序对变形题)
SPOJ COWPIC(逆序对变形题)
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; }
SPOJ COWPIC(逆序对变形题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。