C语言经典题目
发布网友
发布时间：2022-05-29 23:52
共5个回答
热心网友
时间：2024-06-01 01:40
如果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, 这个应该不困难
当然, 如果楼主需要的话, 也可以给出程序
热心网友
时间：2024-06-01 01:41
以本例子说
最快2人过 时间2
最快人回 时间1
最慢2人过 时间10
最快人回 时间2
最快2人过 时间2
一共17
算法就是这样过河以最快2人和最慢2人交替进行，回来时候都是对岸最快的人回来。
ps：这个是哪里的ACM？
这样写出代码不难吧。
就是先将时间排序，然后按上面算法计算。
热心网友
时间：2024-06-01 01:41
#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;
}
热心网友
时间：2024-06-01 01:42
1
4
1 5 2 10
那么最短时间不应该是
5+1+2+1+10=19 么??
我错了?!``
热心网友
时间：2024-06-01 01:42
船是两边来回送人，还是单向送人。
看不懂问题
