NOIP2005 篝火晚会 解题报告
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,... bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗?
对于30%的数据，n <= 1000；
对于全部的数据，n <= 50000。
解题过程：
1.首先感觉是宽搜，但n规模太大肯定不行。
2.自己手动模拟了几次，实在没找到规律。求助于百度。
参考http://wenku.baidu.com/view/878beb64783e0912a2162aa7.html?qq-pf-to=pcqq.c2c
1.首先题目 中(b1, b2,... bm -1, bm)没说是连续的。。
2.把圈拆成序列，初始就是 1 2 3 4 .... n 或者n,n-1,n-2....1(逆时针和顺时针)，根据每个人的愿望可以构造出一个圈，一个圈代表n个序列。。只要找出变成初始序列代价最小的就好。 3.怎样求变成初始序列的最小代价？其实代价就是不在应在位置上的数的个数。。证明方法（不是很严谨）： 把一个不在不在应在位置上的数连一条有向边指向它应该去的位置，这样最终会形成环，只要按照环的顺序取(b1, b2,... bm -1, bm)，就可以使环中的元素全部归位。 （有贪心的味道），代价就是环中元素的个数。由于可能有多个环，只要位置不对的元素必定是环中的一部分，而环和环肯定不会有公共部分，不然的话某个元素可能要去多个位置，或者某个位置有多个元素要去。。所以 代价就是不在应在位置上的数的个数。。由此可以拓展开：交换次数最少的排序方法是选择排序，最少次数就是sum（环的边数-1）。 4.根据3显然可以用O（n^2）的算法求出答案（扫描n个序列）。 但是只能过30%的点。百度上的方法是：任取一个序列，求出每个元素与它应去位置的差值，若为负数就加一个n，可以发现差值相等的元素个数是不变的。
那么只要找出相同差值的最多元素的个数MAX，总有n个序列中一个序列中他们的差值变为0，所以结合3答案就是总人数减去MAX。
最新文章
- Android动画：模拟开关按钮点击打开动画（属性动画之平移动画）
- javascript运动系列第四篇——抖动
- SVG 使用
- [BZOJ2659][WC2012]算不出的算式（几何）
- Linq之延迟加载特性
- hdu 2545(并查集求节点到根节点的距离)
- YTU 2925: 文件操作--文本文件读入
- html之input系列标签
- C3P0数据库连接池的相关bug解决
- python日志输出
- 基于DOM的XSS注入漏洞简单解析
- Docker 基于已有镜像的容器创建镜像
- Webgrid参数格式
- nlpir分词器过期处理
- ie11强制兼容模式打开
- AWS的开发工具包和设备SDK开发工具包
- hdfs一直处于safemode模式
- 大数据入门到精通15--hive 对 date类型的处理
- 201621123018《java程序设计》第14周作业总结
- Xamarin Forms MVVM实现效果说明