论坛
潜水/灌水快乐,沉淀知识,认识更多同行。
ToB圈子
加入IT圈,遇到更多同好之人。
朋友圈
看朋友圈动态,了解ToB世界。
ToB门户
了解全球最新的ToB事件
博客
Blog
排行榜
Ranklist
文库
业界最专业的IT文库,上传资料也可以赚钱
下载
分享
Share
导读
Guide
相册
Album
记录
Doing
搜索
本版
文章
帖子
ToB圈子
用户
免费入驻
产品入驻
解决方案入驻
公司入驻
案例入驻
登录
·
注册
只需一步,快速开始
账号登录
立即注册
找回密码
用户名
Email
自动登录
找回密码
密码
登录
立即注册
首页
找靠谱产品
找解决方案
找靠谱公司
找案例
找对的人
专家智库
悬赏任务
圈子
SAAS
ToB企服应用市场:ToB评测及商务社交产业平台
»
论坛
›
软件与程序人生
›
后端开发
›
Java
›
P2448 无尽的生命
P2448 无尽的生命
汕尾海湾
金牌会员
|
2023-1-12 00:11:19
|
显示全部楼层
|
阅读模式
楼主
主题
554
|
帖子
554
|
积分
1662
题目传送门
题意简述
看到题目显而易见是求逆序对个数。
思路分析
看到数据范围 \(x_i,y_i \le 2^{31}-1\),\(k \le 10^5\)。数据值域大但是个数少,且与数据之间的大小关系有关,因此考虑离散化。
离散化简单介绍
离散化实际就是一种映射,当数据值域过大而个数有限时,可以尝试离散化。
具体过程以此题为例。假设给出这么一组数据
2
123456789 123456
987654321 123456
复制代码
首先将所有出现过的数收集起来,存进 \(a\) 数组,并进行排序,然后再
去重
保存进 \(pos\) 数组当中。
接下来就可以建立映射关系。
将数值大的数在 \(num\) 数组中用数值小的数代替,但各个数之间的大小关系不变
,接下来交换操作先用二分答案在 \(pos\) 数组中检索,然后通过映射在 \(num\) 数组中进行交换。
最终被交换过的数之间的逆序对在 \(num\) 数组中求即可。
被交换的数与未被交换的数之间的逆序对
考虑每个被交换的数对答案的贡献。
设 \(x
本帖子中包含更多资源
您需要
登录
才可以下载或查看,没有账号?
立即注册
x
回复
使用道具
举报
0 个回复
倒序浏览
返回列表
快速回复
高级模式
B
Color
Image
Link
Quote
Code
Smilies
您需要登录后才可以回帖
登录
or
立即注册
本版积分规则
发表回复
回帖并转播
回帖后跳转到最后一页
发新帖
回复
汕尾海湾
金牌会员
这个人很懒什么都没写!
楼主热帖
redis实现主从复制
小白福利 | Window前言
一文了解袋鼠云在实时数据湖上的探索与 ...
Kafka生产者
RabbitMQ 进阶 -- 阿里云服务器部署Rab ...
5分钟安装Kubernetes+带你轻松安装isti ...
手记系列之四 ----- 关于使用MySql的经 ...
在线客服系统源码编译Golang语言下go b ...
java中HashMap的设计精妙在哪? ...
在Ubuntu系统上安装StoneDB数据库 ...
标签云
挺好的
服务器
快速回复
返回顶部
返回列表