C语言经典题目

Question

题目
有N个人想要用一条每次只能坐两人的船过河，因此，需要合理的安排来、回以使所有的人都能顺利过河。每个人过河的速度不同，两个人速度取决于速度较慢的一个。你的任务就是想一个策略让所有的人在最短的时间内均过河。

要求 ：时间限制：1000MS 内存限制：10000KB
通过次数（Accepted）：3 提交次数（Submit）：24

说明：
输入
第一行是一个表示测试用例次数的整数T（1<=T<=20），接下来是T个测试用例。每个测试用例的第一行是一个整数N，第二行包含N个整数代表每个人过河的时间。不会超过1000个人（即N<=1000）并且每个人的过河时间不会超过100秒。

输出
每一个测试用例，输出N个人过河所用的最短总时间。

输入示例
1
4
1 5 2 10

输出示例
17
求代码… 哪位高手有的。往赐教 ……

Answer 1

1.正确的算法:
如果n=3, 过河时间为A+B+C
如果n<=2, 好算, 不费口舌了

如果n>=4, 这个是重点:
每次优先考虑把最慢两人送过河
把n人中最快两人记为A,B, 最慢两人记为C,D(过河时间A<B<C<D), n人问题实质上转换为4人过河问题, 参考到4人过河时的优化,
记AB过河, A回, CD过河, B回, 为方法X, 实质是利用最快两人进行优化, 耗时A+2B+D
记AD过河, A回, AC过河, A回, 为方法y, 实质是利用最快一人来过河, 耗时2A+C+D
每次比较这两个方法, 如果x快, 使用x方法, 如果y快, 则用y, 并且, 一旦某次使用y方法后, 以后都不用比较了, 全部使用y方法过河

2.算法正确性证明:
为什么每次先让最慢两人过河? 因为他们迟早要过河...早过晚过一样, 而晚过的话, 有可能时间不能被优化, 所以选择最先过
为什么是两人, 不是三人? 因为这船一次只能两人, 三人问题和两人问题的优化一样, 所以一次考虑三人毫无意义, 同理, 三人以上不加考虑

为什么某次用y过河后不用再比较xy了?
先看这个例子:

1 99 100 101
用x方法是99+1+101+99= 300
y方法是 101+1+100+1 = 203

y比x快的原因是2A+C+D < A+2B+D, 即 A+C<2B
容易想到, 从此以后A+C都会小于2B了(因为C越来越小)

3.补充:
算法分析就到这里了, 至于具体的程序...楼主既然是ACMer, 这个应该不困难
当然, 如果楼主需要的话, 也可以给出程序

Answer 2

最短时间是这样的
以本例子说
最快2人过 时间2
最快人回 时间1
最慢2人过 时间10
最快人回 时间2
最快2人过 时间2
一共17
算法就是这样过河以最快2人和最慢2人交替进行，回来时候都是对岸最快的人回来。

ps：这个是哪里的ACM？
这样写出代码不难吧。
就是先将时间排序，然后按上面算法计算。

Answer 3

#include<iostream>
#include<algorithm>
using namespace std;
int a[1001];
int main()
{
int t,i,n,fast1,fast2,slow1,slow2,slow3,sum,l,r;
cin>>t;
while(t--)
{
sum=0;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
fast1=a[1];fast2=a[2];slow1=a[n-1];slow2=a[n];slow3=0;
l=1;r=n;
while(n!=0)
{
if(n==1) {sum+=slow2;break;}
if(n==2) {sum+=slow2;break;}
if(n==3) {sum+=(slow2+slow1+fast1);break;}
if(2*fast2>=fast1+slow1) {sum+=(slow1+slow2+2*fast1);r-=2;slow2=a[r];slow1=a[r-1];n-=2;}
else {sum+=2*fast2+fast1+slow2;r-=2;slow2=a[r];slow1=a[r-1];n-=2;}
}
cout<<sum<<endl;
}
return 0;
}

Answer 4

有些不懂...我也是初学者..进来看看
1
4
1 5 2 10
那么最短时间不应该是
5+1+2+1+10=19 么??
我错了?!``

Answer 5

试用例次数的整数T是什么
船是两边来回送人，还是单向送人。
看不懂问题