VIJOS 1008 篝火晚会
发布日期:2022-02-05 18:27:28 浏览次数:13 分类:技术文章

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

描述

佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有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。

格式

输入格式

输入的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。

输出格式

输出包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。

样例

样例输入

43 44 31 21 2

样例输出

2

限制

1s

来源

NOIp2005 第三题

一开始真不会 感觉 这tm怎么做啊。。。

后来自己读题

原来b1,b2......bm与1,2,3......m没有任何关系

b1可以是1 可以是2 也可以是3...

那么这样的话 所有位置不匹配的 一次就可以换对位置!

我们就要去找位置不匹配的最小人数

(据说这是置换群,蒟蒻表示真心不知道。。。)

首先判断-1 假如a想和b在一起 b不想和a在一起 那么肯定不能实现愿望  就输出-1

一开始给的序列是1...n

即f[i]=i

目标序列其实有2个

1想要和l[1],r[1]在一起 可以1,l[1],......,r[1]

也可以1,r[1],.......,l[1]

可以用BFS生成这两个序列g(DFS会爆栈。。。)

然后与一开始的序列比较

因为序列是一个环

1 2 3 4 5

2 3 4 5 1

4 5 1 2 3

是等价的

所以g[i]与i是相对的

如果所有g[i]-i都大于1 那么旋转一下 所有g[i]=i

所以我们不应只认为g[i]=i是符合的

事实上 max{T[k]},(k=g[i]-i , 1<=i<=n)是符合最多的人数

只要都和下标i差同一个数 旋转这个数后 就都和下标相同了

因为c++没有负下标

所以可以 (g[i]-i+n)%n

g[i]-i+n处理负下标

%n防止出现g[i]>i时   g[i]-i+n>0的情况  因为n个人 第1个和数一圈后的第n+1个人其实是一个人

代码如下  生成p序列一开始写的dfs 7个点RE

后怕啊 多亏不是考试。。。

然后写了个比较难看的bfs生成序列

#include
#include
#include
using namespace std;int g[50055][2];int a,b,c;int m,z=999999999;int num[250055],hash=100001;int xulie[50055];bool use[50055][2];int i;void bfs(){ int i=2,ret=0,k; xulie[1]=1; xulie[2]=g[1][0]; use[1][0]=1; if(g[g[1][0]][0]==1)use[g[1][0]][0]=1;else use[g[1][0]][1]=1; while(i<=m) { int now=xulie[i]; for(int k=0;k<=1;k++) if(!use[now][k]) { use[now][k]=1; if(g[g[now][k]][0]==now)use[g[now][k]][0]=1; else use[g[now][k]][1]=1; i++; xulie[i]=g[now][k]; } } memset(num,0,sizeof(num)); for(int a=1;a<=m;a++) { k=(xulie[a]-a+m)%m; num[k]++; ret=max(ret,num[k]); } z=min(z,(m-ret)); i=2; memset(xulie,0,sizeof(xulie));memset(use,0,sizeof(use)); xulie[1]=1; xulie[2]=g[1][1]; use[1][1]=1; if(g[g[1][1]][0]==1)use[g[1][1]][0]=1;else use[g[1][1]][1]=1; while(i<=m) { int now=xulie[i]; for(int k=0;k<=1;k++) if(!use[now][k]) { use[now][k]=1; if(g[g[now][k]][0]==now)use[g[now][k]][0]=1; else use[g[now][k]][1]=1; i++; xulie[i]=g[now][k]; } } ret=0; memset(num,0,sizeof(num)); for(int a=1;a

据说冒泡也可以做?

表示不理解 顺带求讲解

转载地址:https://blog.csdn.net/li412302070/article/details/12910575 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:POJ 3666 Making the Grade
下一篇:TYVJ 1443 油滴扩展

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月05日 19时37分51秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

单系统 台电x80pro_台电x80 pro (ID:E3E6)安装remix OS系统教程整理 2019-04-21
linux存储pdf伟岸_python的reportlab库介绍、制作pdf和作图 2019-04-21
安徽信息技术初中会考上机考试模拟_2020年中小学寒假、考试时间定下了! 2019-04-21
ubuntu 退出anaconda环境_从零开始深度学习第15讲:ubuntu16.04 下深度学习开发环境搭建与配置... 2019-04-21
稳定币usda是哪个发行的_武夷山币装帧款曝光,共4款设计,你喜欢哪款? 2019-04-21
可变车道怎么走不违章_走ETC竟比人工车道贵50%!交警:这3点不知道,吃亏的是自己... 2019-04-21
苹果笔记本的end键_笔记本用户的大烦恼:触控板,想好好用你不容易 2019-04-21
趣玩机器人什么时候成立的_【直播回顾】当我们谈机器人集成调试的时候在谈什么... 2019-04-21
中考大数据大连79_中考大数据 | 大连部分初中2019年中考指标生录取最低分及人数统计!... 2019-04-21
vue 地理位置定位_HTML5地理位置 2019-04-21
pac代理模式什么意思_托管仓库租赁电商仓储运营模式托管什么意思 2019-04-21
validated 验证数组_在 Laravel 中处理请求验证的智能方法 2019-04-21
洞泾智能机器人产业基地_G60科创走廊洞泾人工智能产业基地(核心区块)暨洞泾镇招商人员培训班顺利开班... 2019-04-21
java 拼接路径优雅方式_Java安全编码实践总结 2019-04-21
realme x2 深度测试打不开_搭载65W超级闪充,realme真我X7手机充电评测 2019-04-21
整数取反编程_【每日编程185期】数字的补数 2019-04-21
能用别的软件吗_手机软件能用蓝牙传送吗 2019-04-21
为什么图片要2的倍数_为什么宝宝喜欢流“口水”?这种2种原因父母要知道,建议收藏... 2019-04-21
下载了XAMPP怎样打开MYSQL_xampp mysql安装启动 2019-04-21
pdo转mysql_mysql转mysqli或pdo 2019-04-21