文档章节

火柴排队 归并 or 树状数组

Loi_DL
 Loi_DL
发布于 2016/11/09 21:16
字数 803
阅读 20
收藏 0

http://codevs.cn/problem/3286/

题面在 ↑ 面呢。

题意:让你求两个数列的最小差的平方和最少需要交换几次(只能周围交换)。刚开始听人说是求逆序对,我学了个归并就来搞这个题了。想了半天也没想明白怎么求逆序对啊。然后找了找题解。首先想什么时候保证两个数列差最小,一定是第一个数列第一大的对应第二个数列第一大的...依次类推。这样就可以再开两个数组记录一下他们的编号,然后利用sort结构体按照数的大小从小到大排序,最后开一个数组记录第一个数列中第一大的序号对应在第二个数列中第一大的序号是什么位置既 zh [ xh1 [ i ] ] = xh2 [ i ]  。然后求这个数组的逆序对,然后对答案去%输出

归并排序求逆序对的思想:

二分出两个数组来,保证两个数组都是递增有序的,然后从两个数组中分别取出第一个数字比较,如果第二个数小于第一个数则ans+=第一个数组中剩下的数。正确性自行证明其实显然。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxx=100007;
struct ha
{
	LL x,xh;
}y1[maxx];
ha y2[maxx];
LL zh[maxx],t[maxx];
LL n,ans=0;
void _marge(LL l,LL r)
{
	
	if(l==r) return ;
	LL mid=(l+r)/2;
	_marge(l,mid);
	_marge(mid+1,r);
	LL pl=l,pr=mid+1,p=l;
	while (pl<=mid || pr<=r)
	{
		if(pl>mid)
		{
			t[p]=zh[pr];
			p++;
			pr++;
		}
		else if(pr>r)
		{
			t[p]=zh[pl];
			p++;
			pl++;
		}
		else if(zh[pr]<zh[pl])
		{
			ans+=mid-pl+1;
			t[p]=zh[pr];
			p++;
			pr++;
		}
		else 
		{
			t[p]=zh[pl];
			p++;
			pl++;
		}
	}
	for(int i=l;i<=r;i++)
		zh[i]=t[i];
	return ;
}
LL cp(ha a,ha b)
{return a.x<b.x;}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&y1[i].x);
		y1[i].xh=i;	
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&y2[i].x);
		y2[i].xh=i;	
	}
	sort(y1+1,y1+1+n,cp);
	sort(y2+1,y2+1+n,cp);
	for(int i=1;i<=n;i++)
		zh[y1[i].xh]=y2[i].xh;
	_marge(1,n);
	printf("%lld",ans%99999997);
	return 0;
}

树状数组求逆序对思想:(感谢lc的help)

给每个数组一个序号,然后sort结构体排序。然后按照序号放数。每次放之前用树状数组求一下当前序号的前缀和。ans+=每次前缀和。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxx=100007;
struct ha
{
	LL x,xh;
}y1[maxx];
ha y2[maxx];
ha zh[maxx];
LL n,ans=0;

LL c[1000000];
void change(LL x,LL d)
{
	while(x<=n)
	{
		c[x]+=d;
		x+=x&(-x);
	}
}
LL ask(LL x)
{
	LL ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=x&(-x);
	}
	return ans;
}
LL cp(ha a,ha b)
{return a.x<b.x;}
LL cp2(ha a,ha b)
{return a.x>b.x;}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&y1[i].x);
		y1[i].xh=i;	
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&y2[i].x);
		y2[i].xh=i;	
	}
	sort(y1+1,y1+1+n,cp);
	sort(y2+1,y2+1+n,cp);
	for(int i=1;i<=n;i++)
		zh[y1[i].xh].x=y2[i].xh;
	for(int i=1;i<=n;i++)
		zh[i].xh=i;
	sort(zh+1,zh+1+n,cp2);
	for(int i=1;i<=n;i++)
	{
		ans+=ask(zh[i].xh-1);
		change(zh[i].xh,1);
	}
	printf("%lld",ans%99999997);
	return 0;
}

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
Tableau10.5视频课程之常见图形制作

1.气泡图与文字云 2.条形图 3.面积图 4.折线图 5.直方图 6.帕累托详解 7.树状图 8.凹凸图 9.标靶图 10.饼图+环图+双饼图 11.甘特图 12.盒须图 13.火柴图 14.基本地图+地图柱图+地图饼图 15.雷...

荷露叮咚
2018/03/27
0
0
数据结构与算法--归并排序

数据结构与算法--归并排序 归并排序 归并排序基于一种称为“归并”的简单操作。比如考试可能会分年级排名和班级排名,那么这个年级排名可能是合并了各个班级的排名后对其再排名得到——每个班...

sunhaiyu
2017/10/29
0
0
TimSort排序算法及一个问题分析

TimSort排序算法及一个问题分析 摘要 排序算法简析 问题解析 参考 摘要 简单介绍了传统归并排序算法,以及Java API提供的TimSort优化后的归并排序算法。 并且分析了代码中出现的一个问题原因...

winters1224
2018/06/26
0
0
分治思想之排序算法

分而治之是设计高效算法的一个重要思想。本文主要总结一下分治思想在排序算法中的运用。 排序在商业数据处理和现代科学计算中有着重要的地位,它能够应用于事物处理、组合优化、天体物理学、...

丶legend
2017/10/02
0
0
排序算法-选择,插入,希尔,归并,快排

排序 选择排序 selection 插入排序 insertion 希尔排序 shell 归并排序 快速排序 准备工作 交换方法,供后续调用: 自顶向下的归并排序 如果它能将两个子数组排序,它就能够通过归并两个子数...

rustfisher
2015/12/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【AI实战】手把手教你深度学习文字识别(文字检测篇:基于MSER, CTPN, SegLink, EAST等方法)

文字检测是文字识别过程中的一个非常重要的环节,文字检测的主要目标是将图片中的文字区域位置检测出来,以便于进行后面的文字识别,只有找到了文本所在区域,才能对其内容进行识别。 文字检...

雪饼
今天
5
0
思维导图XMind 8 Pro 绿化方法(附序列号)

按部就班: Step 1 -全新下载最新版本的 Xmind 8(注必须是英文官方的版本,中文代{过}{滤}理网站的版本修改过,无法使用pj); Step 2 -安装完毕后,点击文末的下载按钮下载pj补丁文件包,将...

一只小青蛙
今天
10
0
数据结构(ER数据库)设计规范

表命名规范 表命名的规则分为3个层级,层级之间通过_分割,例如b_r_identity、d_l_identity。规约为: [leavel]_[type]_[name] [leavel] 表示数据库表的层级和功能,分为: s:业务无关的系统...

随风溜达的向日葵
今天
5
0
阿里Sentinel控制台源码修改-对接Apollo规则持久化

https://github.com/alibaba/Sentinel/wiki/%E5%9C%A8%E7%94%9F%E4%BA%A7%E7%8E%AF%E5%A2%83%E4%B8%AD%E4%BD%BF%E7%94%A8-Sentinel 动态规则扩展 https://github.com/alibaba/Sentinel/wiki......

jxlgzwh
昨天
7
0
在Linux系统中创建SSH服务器别名

如果你经常通过 SSH 访问许多不同的远程系统,这个技巧将为你节省一些时间。你可以通过 SSH 为频繁访问的系统创建 SSH 别名,这样你就不必记住所有不同的用户名、主机名、SSH 端口号和 IP 地...

老孟的Linux私房菜
昨天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部