发信人: sino (茶水先生), 信区: Algorithm
标 题: ZSUCPC 2000中山同志们的题解--第一试第3题
发信站: 哈工大紫丁香 (2001年08月27日10:10:30 星期一), 站内信件
发信人: splutter (呆子), 信区: ACMICPC
标 题: [合集]第一试第三题 forgetful
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 19 05:26:13 2001), 站内信件
发信人: woodmen (CS99-:悟得慢), 信区: Programming
标 题: [合集]第一试第三题
发信站: 逸仙时空 Yat-sen Channel (Thu May 17 17:38:51 2001), 站内信件
mk (逐风) 于Fri May 11 18:45:22 2001提到：
第三题：车厢重组（40分）
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站
的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢
的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车
厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一项
重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车厢
排序，屏幕输出最少的步数。
输入样例：
4 3 2 1
输出样例：
6
forgetful (准备梨树中) 于Fri May 11 21:07:32 2001提到：
有点问题，这里的顺序一定是从1到车厢总数的各个整数吗？
【 在 mk (逐风) 的大作中提到: 】
: 第三题：车厢重组（40分）
: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车
站
: 的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车
厢
: 的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的
车
: 厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一
项
: 重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车
厢
: 排序，屏幕输出最少的步数。
: 输入样例：
: 4 3 2 1
: 输出样例：
: …………
forgetful (准备梨树中) 于Fri May 11 21:49:30 2001提到：
搞掂
#include <iostream.h>
#define MAXTRAIN 100
void mvnum(int *nums,int len); //将nums后的len辆移上来
void main()
{
int train[MAXTRAIN];
int i,j,max=1,times=0;
for(i=0;i<max;i++)
{
cin>>train[i];
if(train[i]>max) max=train[i];
}
while(max>1)
{
i=0;
while(train[i]!=max) i++;
times=times+max-i-1;
max--;
mvnum(&train[i],max-i);
}
cout<<times;
}
void mvnum(int *nums,int len)
{
int i=0,temp=*nums;
for(i=0;i<len;i++)
*(nums+i)=*(nums+1+i);
*(nums+len)=temp;
}
【 在 mk (逐风) 的大作中提到: 】
: 第三题：车厢重组（40分）
: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车
站
: 的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车
厢
: 的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的
车
: 厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一
项
: 重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车
厢
: 排序，屏幕输出最少的步数。
: 输入样例：
: 4 3 2 1
: 输出样例：
: …………
menway (我没有钱) 于Fri May 11 22:11:51 2001提到：
sorry,你的题好像解的不对哦，try 1 2 3 5 4,your answer is 0,why?
【 在 forgetful (准备梨树中) 的大作中提到: 】
: 搞掂
: #include <iostream.h>
: #define MAXTRAIN 100
: void mvnum(int *nums,int len); //将nums后的len辆移上来
: void main()
: {
: int train[MAXTRAIN];
: int i,j,max=1,times=0;
: for(i=0;i<max;i++)
: {
: …………
monster@argo (不再堕落，不再�) 于Fri May 11 22:12:48 2001)
提到：
转信站: argo
【 在 menway (我没有钱) 的大作中提到: 】
: sorry,你的题好像解的不对哦，try 1 2 3 5 4,your answer is 0,why?
: 【 在 forgetful (准备梨树中) 的大作中提到: 】
: : 搞掂
: : #include <iostream.h>
ya...the correct answer should be 1
menway (我没有钱) 于Fri May 11 22:15:10 2001提到：
我的程序，思路是利用广度优先搜索，为了方便表示，用字符串表示每一个状态，具体
程序如下。总共63行
const
max=2000;
infile='3.dat'; {输入文件，为了方便，直接输出到屏幕}
type
ty=record
str:string[20];
dep:byte;
end;
var
done,found:boolean;
a:array[1..max] of ty;
st,des:string[20];
head,tail:integer;
i,j,k:byte;
min,temp:char;
f:text;
begin
assign(f,infile);
des:='';
reset(f);
while not(eof(f)) do begin
read(f,i);
des:=des+char(48+i);
end;
close(f);
a[1].str:=des;
a[1].dep:=0;
for i:=1 to ord(des[0]) do begin
min:=des[i];
k:=i;
for j:=i+1 to ord(des[0]) do
if des[j]<min then begin
k:=j;
min:=des[j];
end;
temp:=des[i];
des[i]:=des[k];
des[k]:=temp;
end;
head:=0;
tail:=1;
done:=false;
while (head<>tail) and (not done) do begin
inc(head);
for i:=1 to ord(a[head].str[0])-1 do begin
st:=a[head].str;
st:=copy(st,1,i-1)+st[i+1]+st[i]+copy(st,i+2,255);
found:=false;
for j:=1 to tail do if a[j].str=st then begin found:=true;break;end;
if not found then begin
inc(tail);
if tail>max then begin
writeln('No answer!');
halt;
end;
a[tail].str:=st;
a[tail].dep:=a[head].dep+1;
if st=des then begin done:=true;break;end;
end;
end;
end;
writeln(a[tail].dep);
end.
【 在 mk (逐风) 的大作中提到: 】
: 第三题：车厢重组（40分）
: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车
站
: 的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车
厢
: 的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的
车
: 厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一
项
: 重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车
厢
: 排序，屏幕输出最少的步数。
: 输入样例：
: 4 3 2 1
: 输出样例：
: …………
monster@argo (不再堕落，不再�) 于Fri May 11 22:15:40 2001)
提到：
转信站: argo
【 在 mk (逐风) 的大作中提到: 】
: 第三题：车厢重组（40分）
: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车
站
: 的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车
厢
: 的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的
车
: 厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一
项
: 重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车
厢
: 排序，屏幕输出最少的步数。
: 输入样例：
: 4 3 2 1
: 输出样例：
: …………
这题实际上是求逆序数，不用搜索，对吧？
forgetful (继续健忘) 于Fri May 11 22:16:44 2001提到：
哦，原来输入那里错了
但应该怎样改呢？怎样判断已经输入了全部的顺序？
【 在 menway (我没有钱) 的大作中提到: 】
: sorry,你的题好像解的不对哦，try 1 2 3 5 4,your answer is 0,why?
: 【 在 forgetful (准备梨树中) 的大作中提到: 】
: : 搞掂
: : #include <iostream.h>
forgetful (继续健忘) 于Fri May 11 22:18:17 2001提到：
题目要求是用键盘输入的啊？从文件输入是不难啊，但键盘输入就....
【 在 menway (我没有钱) 的大作中提到: 】
: 我的程序，思路是利用广度优先搜索，为了方便表示，用字符串表示每一个状态，具
体
: 程序如下。总共63行
: const
: max=2000;
: infile='3.dat'; {输入文件，为了方便，直接输出到屏幕}
: type
: ty=record
: str:string[20];
: dep:byte;
: end;
: …………
forgetful (继续健忘) 于Fri May 11 22:19:47 2001提到：
求逆序数有什么好的算法没有？？
【 在 monster (不再堕落，不再�) 的大作中提到: 】
: 【 在 mk (逐风) 的大作中提到: 】
: : 第三题：车厢重组（40分）
: : 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个
车站
: : 输出样例：
: : …………
: 这题实际上是求逆序数，不用搜索，对吧？
mysunshine (雨一直下) 于Fri May 11 22:20:16 2001提到：
模拟
【 在 forgetful (继续健忘) 的大作中提到: 】
: 求逆序数有什么好的算法没有？？
: 【 在 monster (不再堕落，不再�) 的大作中提到: 】
: : 这题实际上是求逆序数，不用搜索，对吧？
mysunshine (雨一直下) 于Fri May 11 22:25:14 2001提到：
不过不是什么好算法。^_^
【 在 mysunshine (雨一直下) 的大作中提到: 】
: 模拟
: 【 在 forgetful (继续健忘) 的大作中提到: 】
: : 求逆序数有什么好的算法没有？？
monster@argo (不再堕落，不再�) 于Fri May 11 22:25:35 2001)
提到：
转信站: argo
【 在 forgetful (继续健忘) 的大作中提到: 】
: 求逆序数有什么好的算法没有？？
: 【 在 monster (不再堕落，不再�) 的大作中提到: 】
: : 这题实际上是求逆序数，不用搜索，对吧？
int f(int *a, int size)
{
int count = 0;
for(int i = 0; i < size; i++)
for(int j = i + 1; j < size; j++)
if(a[j] < a[i]) count++;
return count;
}
menway (我没有钱) 于Fri May 11 22:29:49 2001提到：
hehe,我做得太麻烦了。再贴一个，算法和monster的一样，做了输入处理
var
st,s2:string;
s,max,i,j:byte;
a:array[1..100] of byte;
code:integer;
begin
read(st);
max:=0;
while pos(' ',st)<>0 do begin
s2:=copy(st,1,pos(' ',st)-1);
delete(st,1,pos(' ',st));
inc(max);
val(s2,a[max],code);
end;
inc(max);
s:=0;
val(st,a[max],code);
for i:=1 to max-1 do
for j:=i+1 to max do
if a[j]<a[i] then inc(s);
writeln(s);
end.
【 在 monster (不再堕落，不再�) 的大作中提到: 】
: 【 在 forgetful (继续健忘) 的大作中提到: 】
: : 求逆序数有什么好的算法没有？？
: int f(int *a, int size)
: {
: int count = 0;
: for(int i = 0; i < size; i++)
: for(int j = i + 1; j < size; j++)
: if(a[j] < a[i]) count++;
: return count;
: }
Holmaming (更加风采动朝端) 于Sat May 12 11:36:10 2001提到：
有个疑问，若就按冒泡排序这样来做，有反例吗？
【 在 mk (逐风) 的大作中提到: 】
: 第三题：车厢重组（40分）
: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车
站
: 的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车
厢
: 的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的
车
: 厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一
项
: 重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车
厢
: 排序，屏幕输出最少的步数。
: 输入样例：
: 4 3 2 1
: 输出样例：
: …………
--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]