【luogu AT1218】たのしい家庭菜園 / 交换(贪心)(树状数组)
数组 贪心 交换 Luogu 树状 家庭
2023-09-27 14:28:27 时间
たのしい家庭菜園 / 交换
题目链接:luogu AT1218
题目大意
给你一个数组,你每次可以交换两个相邻的位置。
问你要交换多少次才能使得这个数组变成先上升后下降的形式。
思路
不难看到一个贪心的做法,肯定是从小到大每次把它移到左边或者右边。
那你就可以分别求出移到左边和右边的费用,然后每个都选最小值的即可。
然后移到一边的费用大概就是比它大的个数(因为这些要被移动出来),那这个我们用两次树状数组求即可。
代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, a[300001], f[300001], g[300001], tr[300001];
int b[300001];
ll ans;
void Add(int x, int y) {//树状数组
for (; x <= n; x += x & (-x)) tr[x] += y;
}
int Ask(int x) {
int re = 0;
for (; x; x -= x & (-x)) re += tr[x];
return re;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
memcpy(b, a, sizeof(b));
sort(b + 1, b + n + 1);//离散化
int nn = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
for (int i = 1; i <= n; i++) {
f[i] = i - 1 - Ask(a[i]);
Add(a[i], 1);
}
for (int i = 1; i <= n; i++) Add(a[i], -1);
for (int i = n; i >= 1; i--) {
g[i] = n - i - Ask(a[i]);
Add(a[i], 1);
}
for (int i = 1; i <= n; i++)
ans += min(f[i], g[i]);
printf("%lld\n", ans);//Atcoder特色换行?(似乎不换行会WA
return 0;
}
相关文章
- 连续子数组最大和
- 合并数组 扩展运算符
- JavaScript中31个数组方法,包括es5,es6新增方法(关注收藏,持续更新)
- Linux-Shell编程之数组操作
- LeetCode_双指针_中等_1764.通过连接另一个数组的子数组得到一个数组
- LeetCode_贪心算法_中等_1775.通过最少操作次数使数组的和相等
- LeetCode_前缀树_贪心算法_中等_421.数组中两个数的最大异或值
- Distinct Substrings SPOJ - DISUBSTR 后缀数组
- HDU 4691 Front compression (2013多校9 1006题 后缀数组)
- LeetCode·每日一题·1775.通过最少操作次数使数组的和相等·贪心
- LeetCode·每日一题·1822.数组元素积的符号·模拟
- LeetCode·1005.K次取反后最大化的数组和·贪心
- LeetCode·53.最大子数组和·贪心
- js--非循环方式填充数组
- 牛客练习赛3 F - 监视任务——贪心&&树状数组
- 二维数组旋转