What Goes Up Must Come Down
2024-10-19 18:42:53
题目描述
给定一个序列, 求出将此序列变换为单调递增、单调递减 或者先增后减
样例1
输入
7
3 1 4 1 5 9 2
输出
3
样例2
输入
9
10 4 6 3 15 9 1 1 12
输出
8
分析
本题相当于是有一个峰值, 峰值两边的都单调递减
我们可以用树状数组求出对于所有的数字处于峰值左边或者右边所需要的交换次数
对于这两种情况取一个最小值即可
CODE
#include <iostream>
#define lowbit(i) i & -i
#define mset(a) for(int i = 0; i <= px; i ++ ) a[i] = 0
using namespace std;
const int N = 1e5 + 10;
int n, px;
int a[N], tr[N], cnt[N];
void add(int x) {
for(int i = x; i <= px; i += lowbit(i) ) tr[i] ++;
}
int sum(int x) {
int ans = 0;
for(int i = x; i; i -= lowbit(i)) ans += tr[i];
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++ ) {
cin >> a[i];
px = max(a[i], px);
}
for(int i = 1; i <= n; i ++ ) {
cnt[i] = sum(px) - sum(a[i]);
add(a[i]);
}
mset(tr);
for(int i = n; i; i -- ) {
cnt[i] = min(sum(px) - sum(a[i]), cnt[i]);
add(a[i]);
}
long long ans = 0;
for(int i = 1; i <= n; i ++ ) ans += cnt[i];
cout << ans << endl;
return 0;
}
最新文章
- Docker容器环境下ASP.NET Core Web API应用程序的调试
- Linux安装搜狗拼音输入法
- The first DP!
- 天气预报API获取
- DataProcessing
- [Express] Level 1: First Step
- (转载)Undefined variable: PHP_SELF的问题解决方法
- Tp框架获取客户端IP地址
- Struts2中实现随机验证码
- Playfair 加密
- BJOI2018 简要题解
- 同步下的资源互斥:停运保护(Run-Down Protection)机制
- 快速为git添加一个用户
- python中 os._exit() 和 sys.exit(), exit(0)和exit(1) 的用法和区别
- 阿里八八β阶段Scrum(2/5)
- vue的使用1
- A1025. PAT Ranking
- pytorch定义一个简单的神经网络
- 依赖倒置(DIP)、控制反转(IOC)和依赖注入(DI)
- 【12】外观模式(Facade Pattern)
热门文章
- 第二十七个知识点:什么是对称密码加密的AEAD安全定义?
- CS5266 Type-C转HDMI+PD3.0+USB3.0 三合一拓展坞电路设计
- Two pointer方法
- css基础-1
- hexo 升级5.4.0出现错误解决方法-hexo-theme-butterfly
- CentOS 7 连接不到网络解决方法(设置静态ip)
- Powershell 【控制台常用方法】
- [Docker] 制作并运行 Nginx 镜像
- PPT2010制作翻牌动画
- 硬核 - Java 随机数相关 API 的演进与思考(上)