当前位置： 移动技术网 > IT编程>开发语言>C/C++ > P2995 [USACO10NOV]牛的照片(树状数组,逆序对)

P2995 [USACO10NOV]牛的照片(树状数组,逆序对)

2019年10月21日  | 移动技术网IT编程  | 我要评论

暗焰余烬,反斗天庭主题曲,生死相许部长夫人

题目：

p2995 [usaco10nov]牛的照片cow photographs
p4545 [usaco10nov]奶牛的图片cow photographs
sp7809 cowpic - cow photographs

解析：

一个环形的逆序对
最大的数可以放在最小的数的左边而不贡献逆序对
所以就可以在原序列的基础上，从小到大枚举序列中的数，并且让这个数\(+n\)，变成最大的数，将某个数加\(n\)后，左边的数就不对它贡献逆序对了，所以逆序对个数减去\((pos[i]-1)\)，而其右边会贡献\((n-pos[i])\)个逆序对，这样从小到大枚举并取min就好了
\(pos[i]\)表示\(i\)在序列中的位置
注意开long long

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int n = 5e5 + 10;
const int inf = 0x3f3f3f3f;

int n, m, ans, sum;
int a[n], t[n], pos[n];

namespace bit {
    inline int lowbit(int x) {return x & -x;}
    void add(int x, int y) {for (; x <= n; x += lowbit(x)) t[x] += y;}
    int query(int x) {
        int ret = 0;
        for (; x; x -= lowbit(x)) ret += t[x];
        return ret;
    }
}

using namespace bit;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i;
    for (int i = 1; i <= n; ++i) {
        add(a[i], 1);
        sum += i - query(a[i]);
    }
    ans = sum;
    for (int i = 1; i <= n; ++i) {
        sum = sum - (pos[i] - 1) + (n - pos[i]);
        ans = min(ans, sum);    
    }
    cout << ans;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网