博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj2299 二分思想
阅读量:6595 次
发布时间:2019-06-24

本文共 1737 字,大约阅读时间需要 5 分钟。

poj2299   http://poj.org/problem?id=2299

题意: 
一个含有n个数的数组, 每次只能交换相邻的两个数, 求最少操作多少次可以使该数组变成一个有序数组(从小到大)。 
分析: 
先说一下归并排序吧。 二分的思想, 就是将一元素集合分割成两个或更多个子集合,对每一个子集合分别排序,然后将排好序的子集合归并为一个集合。看图理解会好一点! 
这里写图片描述

归并排序核心操作:将一维数组中前后相邻的两个有序序列归并为一个有序序列。

那看一下我们这题, 其实就是在归并排序的过程中顺便计算一下移动次数, 就好了。 举个例子:例如图中前半部分数组{8,3,2,9}, 先分为两部分{8,3} 和{2,9} 。 {8,3}又分为{8} 和{3}, 8又在3前面所以合并8,3需要移动一次 sum= 1, {2,9}分为{2} he {9}, 本来就是有序的所以合并2,9不需要移动 sum= 1; 接下来这一步就该合并{3,8} 和{2,9}了。 2前面有两个比它大的数,所以要交换两次, 2才能排到第一位 sum = sum+2 = 3; 9比前面的都大就不用交换啦 sum= 3。

 

#include
#include
#include
#include
using namespace std;const int N = 500005;__int64 sum, a[N], c[N];int n;void merge1(int low, int high, int mid){ int i = low, j = mid + 1; int k = 0; while((i <= mid) && (j <= high)) { if(a[i] <= a[j]) { c[++k] = a[i]; i++; } else if(a[i] > a[j]) { c[++k] = a[j]; j++; sum += (mid - i + 1); } } while(i <= mid) c[++k] = a[i++]; while(j <= high) c[++k] = a[j++]; if(low < high) { for(int i = high; i >= low; i--) { a[i] = c[k]; k--; } }}//通过ac()不断将数组划分为更小的区间,再通过merge1()将划分的数组再合并回来, 并且合并的时候使其变得有序void ac(int low, int high){ if(low < high) { int mid = (low + high) / 2; ac(low, mid); ac(mid + 1, high); merge1(low, high, mid); }}int main(){ while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%I64d", &a[i]); sum = 0; ac(1, n); printf("%I64d\n", sum); } return 0;}
View Code

 

转载于:https://www.cnblogs.com/wd-one/p/4495788.html

你可能感兴趣的文章
使用IntelliJ IDEA开发SpringMVC网站(四)用户管理
查看>>
js 验证中文
查看>>
Linux下运行java DES AES加解密
查看>>
牛津词典 2018 年度词汇 ——「有毒」!
查看>>
Android Arcface人脸识别sdk使用工具类
查看>>
android studio单个工程文件的代理设置
查看>>
我的友情链接
查看>>
一行命令获取当前JVM所有可设置的参数以及当前默认值
查看>>
Linux mint 14下的powerDNS+mysql+powerAdmin搭建个性DNS域名解析服务器
查看>>
Red Hat EnterPrise Linux 5.4下web服务器的综合使用(普通站点、虚拟主机、安全性、...
查看>>
unbantu安装 mysql --- 百度云
查看>>
JS中的默认行为
查看>>
从oracle到mysql,主从到分库,一个普通项目数据库架构的变迁
查看>>
selenium层级定位及鼠标键盘操作
查看>>
SpringBoot跨域问题解决方案
查看>>
(转载)hibernate3.0配置文件模板
查看>>
46、练习:输出指定目录下的所有文件名称
查看>>
IP地址与数字地址相互转换
查看>>
Knockout.Js官网学习(创建自定义绑定)
查看>>
python 抽象类、抽象方法、接口、依赖注入、SOLIP
查看>>