当前位置: 首页 > news >正文

10.1考试T4(swap)题解

题目描述

\(link\)

小 D 正在研究交换。

小 D 认为一个整数序列是好的,当且仅当它先(不严格)上升,后(不严格)下降。

形式化地,我们认为序列 \(𝑎_1,𝑎_2,...,𝑎_𝑛\) 是好的,当且仅当存在某个 \(𝑘∈[1,𝑛]\),使得对于任意
\(1 ≤𝑖 <𝑘\),有 \(𝑎_𝑖 ≤𝑎_𝑖+1\),且对于任意 \(𝑘≤𝑖<𝑛\),有 \(𝑎_𝑖 \ge 𝑎_𝑖+1\)

小 D 得到了一个长度为 𝑛 的序列 \(𝑎_1,𝑎_2,...,𝑎_𝑛\),他想让这个序列变成好的。

小 D 每次可以交换相邻的两个元素。因为交换很累,所以小 D 想知道,他最少需要交换多少次。

这下小 D 不会了,请你帮帮他。

subtask1(15pts):\(𝑛 ≤ 10\)

subtask2(20pts):\(𝑛 ≤ 500\)

subtask3(15pts):\(𝑛 ≤ 5000\)

subtask4(15pts):\(𝑛 ≤ 10^5\)

subtask5(20pts):\({𝑎}\) 是一个 \([1,𝑛]\) 的排列。

subtask6(15pts):无特殊限制。

对于 100% 的数据,\(1≤𝑛≤3×10^5,1≤𝑎_𝑖 ≤𝑛\)

方法

考虑贪心。

对于一个序列,如果我们要让他变好,其最小值一定会被移到最左边或最右边。移到最左边或最右边就取决于移到哪边需要的次数最少。

于是,我们再考虑分治。每次将对序列中最小的数移到最边上,给 \(ans\) 加上移动次数,并将这个数删掉。这样,我们就又得到了一个序列。对序列进行这样的重复操作,直到 \(n\) 个数全部被删除,输出 \(ans\) 即可。

但是,当我们有很多个并列最小的数时,对这些数删除的顺序是有讲究的。每次只能删除最左边或最右边的数,否则一定会产生两个相等的数交换位置的情况。这无疑是无意义的,会使答案不是最优。并且,应删除最左边或最右边中删除所需次数更少的一边。这样,才能保证后面被删除的数是最优的。

时间复杂度:\(O(n^2)\)

优化

观察到 \(n\) 最大能达到 \(3×10^5\)\(n ^ 2\) 是肯定卡不过去的。这时候我们便需要优化。

我们可以使用平衡树\(fhq-treap\)其实树状数组也可以用,又快又好些,吹普常数大的没边,但我是范浩强吹普死忠粉,我就要用。 维护 \(treap\) 对一个序列分成三段,一段为要删的数前的数,一段为其自己,一段为其后面的数,启动次数就是前面的数的 \(size\) 和后面的数的 \(size\)\(min\),然后再将前后的数合并,即将要删掉的数删掉。重复操作即可,细节看代码就行。我对我马蜂的美丽程度还是很自信的。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define usd unsigned
#define el cout << '\n'
#define lowbit(x) (x & (-x))
const int ranmod = 1e7;
#define random ((rand() * rand()) % ranmod)
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
// void init();
void main_();
signed main() {ios :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);// freopen(".in", "r", stdin);// freopen(".out", "w", stdout);int t = 1;// cin >> t;while(t--) {// init();main_();}AK;
}
const int mod = 95225987, maxn = 3 * 1e5 + 18;int ch[maxn][2], rnd[maxn], val[maxn], siz[maxn], tot, rt;
int add(int num) {tot++;ls(tot) = rs(tot) = 0;rnd[tot] = random;siz[tot] = 1;val[tot] = num;return tot;
}
void push_up(int i) {siz[i] = siz[ls(i)] + siz[rs(i)] + 1;
}
int merge(int l, int r) {if(l * r == 0) return l + r;int res = 0;if(rnd[l] < rnd[r]) {res = l;rs(l) = merge(rs(l), r);} else {res = r;ls(r) = merge(l, ls(r));}push_up(res);return res;
}
void split(int rt, int v, int &l, int &r) {if(rt == 0) {l = 0, r = 0; AC;}if(val[rt] <= v) {l = rt;split(rs(l), v, rs(l), r);push_up(l);} else {r = rt;split(ls(r), v, l, ls(r));push_up(r);}   
}
int show(int id) {int a, b, mid;split(rt, id, a, b);split(a, id - 1, a, mid);int res = min(siz[a], siz[b]);debug(siz[a]), debug(siz[b]);rt = merge(a, merge(mid, b));return res;
}
int del(int id) {int a, b, mid;split(rt, id, a, b);split(a, id - 1, a, mid);int res = min(siz[a], siz[b]);debug(siz[a]), debug(siz[b]);rt = merge(a, b);return res;
}int n, ans = 0;
map <int, deque <int> > a;void main_() {cin >> n;for(int i = 1; i <= n; i++) {int num;cin >> num;rt = merge(rt, add(i));a[num].push_back(i);}for(auto tmp : a) {while(!tmp.second.empty()) {if(tmp.second.size() == 1) {ans += del(tmp.second.front());tmp.second.pop_front();} else  {int l = show(tmp.second.front()), r = show(tmp.second.back());if(l <= r) {ans += del(tmp.second.front());tmp.second.pop_front();} else {ans += del(tmp.second.back());tmp.second.pop_back();}}}}cout << ans; el;
}
http://www.hskmm.com/?act=detail&tid=22554

相关文章:

  • 基本分段存储管理方式
  • 专题:2025零售数字化与即时零售竞争洞察报告|附130+份报告PDF、数据仪表盘汇总下载
  • 2025/10/1图论
  • 详细介绍:Python 豆瓣TOP250 爬虫类讲解
  • springboot用jar启动能访问,但是打成war,部署到tomcat却访问不到 - 详解
  • 用AirPods控制的创新iPhone游戏:RidePods技术解析
  • oppoR9m电话号码盘对应工程模式
  • 常量
  • Index of /ubuntu-releases/25.10/
  • P10364 [PA 2024] Dzielniki 题解
  • 20251001 之所思 - 人生如梦
  • 25普及联考day6爆炸记
  • unity面向组合开发一:面向对象(OOP)与面向组合(EC)
  • 两级页表
  • 复健。(10月,OI)
  • 实用指南:自动驾驶中的传感器技术55——USS(1)
  • 市场交易反心理特征之三:日内假反转
  • 实用指南:云服务器 + Jenkins 实现项目自动化部署与上线
  • Linux 中awk命令如何统计每行指定字符出现的次数
  • 常系数齐次微分方程
  • 变量
  • 具有快表的地址变换机构
  • 关于子集的枚举与高维前缀和
  • HyperWorks 14.0 轮毂仿真全流程详细教程
  • 原来的OJ怎么没了?
  • 【Linux】库的链接与加载 - 详解
  • CSP-S模拟26
  • 存在是必然的有机系统,好事多磨,心诚则灵
  • 2025 年陶土砖厂家权威推荐 TOP 品牌排行榜,劈开 / 红色 / 干挂 / 砌筑 / 仿古 / 透气 / 耐火 / 异型 / 装饰 / 外墙陶土砖产品厂家推荐
  • AGC015E Mr.Aoki Incubator