主题：[ACM]无聊的排序
rickone
[专家分：15390] 发布于 2005-05-13 19:56:00
无聊的排序
Time Limit:2s Memory Limit:1000k
Total Submit:352 Accepted:150
--------------------------------------------------------------------------------
Problem
你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数,需要他把这些数按升序排列。你可以每次交换两个数的位置,而一次交换的代价被定义成被交换的两个数的和。写一个程序,用最小的交换代价和来帮助弟弟完成这项无聊的排序工作。
Input
第一行为一个数N(N<=100),第二行为互不相同的N个数,有多组测试数据,N为0时结束。
Output
输出一个数，为最小的交换代价和
Sample Input
6
8 4 5 3 2 7
0
Sample Output
34
Source
ACM
回复列表 （共15个回复）
沙发
davidw017 [专家分：4170] 发布于 2005-05-13 20:02:00
上来就做 1125 啊……这题好像有些难度
板凳
davidw017 [专家分：4170] 发布于 2005-05-13 20:06:00
强烈建议做 1004，很经典的 dfs/dp 题
Catchup rickone
User Name: davidw017
Solved: 41
Submitted: 114
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1022 1023 1024 1025 1027 1028 1031 1037 1044 1045 1047 1050 1055 1067 1072 1081 1118 1121 1126 1131
--------------------------------------------------------------------------------
User Name: rickone
Solved: 25
Submitted: 97
1000 1001 1002 1003 1005 1006 1007 1008 1009 1010 1012 1013 1014 1015 1018 1019 1022 1023 1024 1025 1027 1028 1030 1032 1059
--------------------------------------------------------------------------------
Differs:
More:
1004 1011 1016 1017 1020 1031 1037 1044 1045 1047 1050 1055 1067 1072 1081 1118 1121 1126 1131
Less:
1030 1032 1059
3 楼
fengfeng0222 [专家分：1790] 发布于 2005-05-14 00:40:00
想问一下这是什么错误啊！我提交上去就得到错误的答案．warning: return type defaults to `int'
4 楼
rickone [专家分：15390] 发布于 2005-05-14 15:38:00
呵呵~~干嘛把我的‘战绩’拿出来啊，我K掉的题不多啊
没什么时间，我还要准备软考啦
这题主要是贪心策略的问题，我昨天想了一个不对，还要改进
1004？那个什么导弹的？
5 楼
rickone [专家分：15390] 发布于 2005-05-14 17:44:00
#include<iostream.h>
inline void swap(int &a,int &b){int t=a;a=b;b=t;}
void ssort(int *ord,int n)
{
for(int i=0;i<n-1;++i)
for(int j=i+1;j<n;++j)
if(ord[j]<ord[i])swap(ord[j],ord[i]);
}
int getweight(int *ord,int *sor,int n)
{
int i,j,t;
if(!n)return 0;
if(ord[n-1]==sor[n-1])return getweight(ord,sor,n-1);
for(i=0;i<n;++i)if(sor[i]==ord[n-1])break;
for(j=0;j<n;++j)if(sor[j]==ord[i])break;
if(ord[j]==sor[n-1]&&sor[j]<sor[n-1])
{
t=sor[n-1]+sor[j]*2+sor[i];
swap(sor[n-1],sor[j]);
swap(sor[n-1],sor[i]);
return t+getweight(ord,sor,n-1);
}
t=sor[n-1]+sor[i];
swap(sor[n-1],sor[i]);
return t+getweight(ord,sor,n-1);
}
int main()
{
int sor[100],ord[100],n;
while(1)
{
cin>>n;
if(n==0)return 0;
for(int i=0;i<n;++i){cin>>sor[i];ord[i]=sor[i];}
ssort(ord,n);
cout<<getweight(ord,sor,n)<<endl;
}
}
那个策略选择到底是什么条件？
这个是WrongAnswer
6 楼
rickone [专家分：15390] 发布于 2005-05-14 17:49:00
3楼的，出错可以看出错信息的，点击它就可以看到。
7 楼
codepk [专家分：2800] 发布于 2005-05-14 18:24:00
那么什么acm的哪里有啊？哪里注册.......
8 楼
rickone [专家分：15390] 发布于 2005-05-14 18:30:00
http://acm.tongji.edu.cn
9 楼
codepk [专家分：2800] 发布于 2005-05-14 18:51:00
收到~~感谢~~~
10 楼
fengfeng0222 [专家分：1790] 发布于 2005-05-14 19:28:00
呵呵，谢谢楼主提醒．我已经知道错什么了．原来用Ｃ语言做int main(){……return 0;}我没有在函数前加类型的习惯。各位准备去做题的兄弟，记住不要犯我这样的的错误哦。
我来回复
您所在位置：