AtCoder Beginner Contest 261 F // 树状数组
2024-10-11 12:28:40
题目链接:F - Sorting Color Balls (atcoder.jp)
题意:
有n个球,球有颜色和数字。对相邻的两球进行交换时,若颜色不同,需要花费1的代价。求将球排成数字不降的顺序,所需的最小代价。
思路:
将完成排序所需的最小代价记作 cost,将颜色不同的逆序对( i < j && xi > xj && ci ≠ cj )数量记作 cnt ,则有 cost = cnt。证明如下:
可以构造出一种所需花费为 cnt 的排序方案:将这n个球按颜色切分,即切分成若干个颜色相同的连续区间,那么将每个区间进行排序,不需要花费任何代价,然后再进行冒泡排序,则花费代价恰为 cnt。因此有 cost ≧ cnt 。
再证明 cost ≤ cnt :依然先将各个颜色相同的连续区间进行排序,那么不考虑颜色时,总的逆序对变为 cnt 。每次进行相邻数交换,则逆序对数量的变化可能为:+1、0、-1,那么要让逆序对数量变为 0,至少需要 cnt 次交换,因此有 cost ≤ cnt。
那么只需要求出 cnt:求出不考虑颜色时逆序对数量 totalCnt,在求出对于各个颜色,颜色相同的逆序对数量Cnti,因此:cnt = totalCnt - ∑Cnti 。
然后求逆序对,就是树状数组的经典应用了。
代码:
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) (x & -x)
using namespace std; const int N = 300010; int n, c[N];
vector<int> v[N];
int tr[N]; void add(int x, int c)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
} LL sum(int x)
{
LL res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
} int main()
{
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
for(int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
v[0].push_back(x); //v[0]存储不考虑颜色时的值,后续求出不考虑颜色时的逆序对
v[c[i]].push_back(x); //v[ci]则存储考虑颜色时的值,后续求出相同颜色下的逆序对
} LL ans = 0;
for(int i = 0; i <= n; i++) {
for(auto& x : v[i]) {
ans = ans + (i ? -1 : 1) * (sum(n) - sum(x));
add(x, 1);
}
for(auto& x : v[i]) add(x, -1);
}
cout << ans << endl; return 0;
}
最新文章
- Firefly安装ROS及ssh远程登录配置
- eclipse 安装git
- 《Linux内核设计与实现》读书笔记 - 目录 (完结)【转】
- ACCESS的System.Data.OleDb.OleDbException: INSERT INTO 语句的语法错误
- linux下查看进程内存使用情况
- GNU scientific library
- centos7服务器无GUI情况下安装使用Xvfb、selenium、chrome和selenium-server
- mongoDB 文档概念
- python学习笔记3-列表
- java基础学习总结——equals方法
- DNN网络(二)反向传播算法
- apache commons pool
- 个人tools封装
- ScrollView中嵌套ListView的问题
- CrackMe破解系列第一番Acid_burn
- ORM注意点
- NYOJ 163 Phone List (字符串处理 字典树)
- spray-json
- BZOJ4237 稻草人(分治+树状数组+单调栈)
- html相对定位绝对定位