P2995 [USACO10NOV]牛的照片(树状数组,逆序对)
2019-10-25 06:26:25来源:博客园 阅读 ()
P2995 [USACO10NOV]牛的照片(树状数组,逆序对)
题目:
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;
}
原文链接:https://www.cnblogs.com/lykkk/p/11712058.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:实验作业
- 长乐培训Day1 2019-08-16
- P1583 魔法照片 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash