P1966 [NOIP2013 提高组] 火柴排队

2023-10-27 14:59

本文主要是介绍P1966 [NOIP2013 提高组] 火柴排队,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

洛谷的一道原题,方法有很多,树状数组以及排序,对刚学树状数组的人来说用排序会比较好理解。

本题最重要的结论就是,要保证两个数组中相同位置的差最小,但是不一定两个数组中数值相同,所以只需要保证相同位置放的数都是当前数组中第i小的,也就是第一个数组里面第i小数和第二个数组中第i的数放的位置要相同,这个地方搞明白之后,只需要找到最小移动次数,这个时候就简单了用归并排序+逆序对即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define x first
//#define y second
#define int long long
using namespace std;typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e8 - 3;
const int N = 1e5+ 10;int n, m;typedef struct {int a, b;
}aa; bool cmp(aa a, aa b)
{return a.a < b.a; 
} int s[N], f[N], g[N], sum; void merge_sort(int l, int r)
{if(l >= r) return ;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r){if(s[f[i]] <= s[f[j]]) g[k ++] = f[i ++];else{g[k ++] = f[j ++], sum += mid - i + 1;sum %= mod;}}while(i <= mid) g[k ++] = f[i ++];while(j <= r) g[k ++] = f[j ++];for(i = l, j = 0; i <= r; i ++, j ++)f[i] = g[j]; 
}
aa o[N], p[N];
inline void sovle()
{cin >> n;for(int i = 0; i < n; i ++) {cin >> o[i].a;o[i].b = i;}for(int i = 0; i < n; i ++) {cin >> p[i].a;p[i].b = i;}stable_sort(o, o + n, cmp);stable_sort(p, p + n, cmp);for(int i = 0; i < n; i ++)s[i] = p[i].b; // 找出来第二个数组中第i小的数的位置for(int i = 0; i < n; i ++)f[o[i].b] = i; // 找到第一个数组中每个位置都是第几小的merge_sort(0, n - 1);	cout << sum << endl;
}
signed main(void)
{IOS;int t = 1;
//  cin >> t;while(t --) sovle();return 0;
}

 

这篇关于P1966 [NOIP2013 提高组] 火柴排队的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/286431

相关文章

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

火柴游戏java版

代码 /*** 火柴游戏* <p>* <li>有24根火柴</li>* <li>组成 A + B = C 等式</li>* <li>总共有多少种适合方式?</li>* <br>* <h>分析:</h>* <li>除去"+"、"="四根,最多可用火柴根数20根。</li>* <li>全部用两根组合成"1",最大数值为1111。使用枚举法,A和B范围在0~1111,C为A+B。判断</li>** @

如何提高开发的效率,让老板不知所措的给你发工资

设计模式 UML JSP 编程 数据结构 1.你可能会常常发现,写了一段代码后,编译程序时是一大堆的出错 (原因:语法不熟)  ──别担心,这是每个程序员必须经历的事,这时候你就需要更大的耐心及细心,对每一行代码进行仔细人阅读并改正,这个很重要,这可以培养你的理解代码能力,所以要常读程序,不要等到程序运行以后才知道你的程序的结果。  ──如何避免:在写代码以前,要认真的学习计算机语

Java开发实例大全提高篇——Applet的应用

开发十年,就只剩下这套架构体系了! >>>    第21章  Applet的应用 21.1  Applet在html中的使用 实例549  在html中显示Applet HtmlShowApplet.java     public void paint(Graphics g){         g.drawString("html文件已经运行", 50, 50);// 绘制文本

Java开发实例大全提高篇——Java安全

开发十年,就只剩下这套架构体系了! >>>    第6篇  Java安全与Applet应用篇 第20章  Java安全 20.1  Java对称加密 实例531  使用BASE64加密     public static String encryptBASE64(byte[] data) {         //加密数据         return (new BASE64Encoder()

2024国赛论文拿奖快对照这几点及评阅要点,勿踩雷区!(国赛最后冲刺,提高获奖概率)

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 2024“高教社杯”全国大学生数学建模竞赛已过去第三个夜晚,小伙伴们都累了没有,如果感到思维滞涩,别忘了稍作休息,放松一下自己,准备迎接国赛非常重要的收尾阶段——论文。 国赛这几天的努力最后都

看病要排队这个是地球人都知道的常识

归纳编程学习的感悟, 记录奋斗路上的点滴, 希望能帮到一样刻苦的你! 如有不足欢迎指正! 共同学习交流! 🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言​📝唯有付出,才有丰富的果实收获! 看病要排队这个是地球人都知道的常识。 不过经过细心的0068的观察,他发现了医院里排队还是有讲究的。0068所去的医院有三个医生(汗,这么少)同时看病。而看病的人病情有轻重,所以不能根据简单的先来

C++提高编程三(vector容器、deque容器)

文章目录 vector容器vector赋值操作vector容量和大小vector插入和删除vector数据存取vector互换容器vector预留空间deque容器构造函数deque赋值操作deque大小操作deque 插入和删除deque 数据存取deque 排序 vector容器 vector容器数据结构和数组相似,也称为单端数组。区别在于数组是静态空间,vector可以