整数 inpu tel assign roc con 题目 read
"假舟楫者,非能水也,而绝江河。" 这句话说的是,借助渡船的人,不是会游水,却能横渡江河。
会游水的人反而不一定能顺利地横渡江河。由于江面风浪很大,他们必须潜泳渡河。这就必须用到氧气瓶。氧气瓶当然是出题人买的,而出题人没钱,所以只买了一个。这种氧气瓶有两个输出氧气的管道,最多可供两个人同时过河;其中的氧气是无限的。
显然每次应该有两个人过河,再派对岸的一个人把氧气瓶送回来。需要注意的是,已经横渡到对岸的所有队员都可以送回氧气瓶。
现在给定你每个人渡河所需的时间,要你求出,按照以上方案把所有人送到对岸,所需的最短时间。两个人一起过河的时候,所需的时间等于慢的人所用时间。
【输入文件】第一行,一个正整数 n。
其余 n 个正整数,在第 2 行,相邻两个整数之间用一个空格隔开。
【输出文件】一行 1 个整数,表示所用的最短时间。
【样例输入】
3
1 3 4
【样例输出】8
【数据规模和约定】
对于 20% 的数据,n<=10
对于 100% 的数据,文件中的所有整数 <=1000
【题解】
本题非常的奇怪,一拿到题目首先想到的贪心方法就是以 1 号做中转,每次由 1 号送一个人到对岸,再从对岸送回氧气瓶。
典型的例子是这组数据: 1 2 9 9
最优的方法是 1 与 2 号过去,1 号回来,3 与 4 号过去,2 号回来,1 与 2 号过去。这个方案花费是 16。如果按照原先的方案,花费是 22。
但是,绝对的存在反例!
典型的例子是这组数据:1 9 9 9
原先的方案最佳(29),新方案反而差(37)。
经过仔细观察,我们发现一个事实,对岸的人只有两个过河时间最小的人有意义。
这里的意义实质上是由两个过河时间最小的人来决定最优解。
假定现在我们现在需要挨个过河,有 2+2=4 个人;
下标 分别是 1 2 i-1 i
有两种方法:
①1 号自己把两个人带过去。
1 i(1 和 i 共用氧气筒) 1(1 送还氧气筒) 1 i-1(1 把 i-1 送到对岸) 1(再回来准备下一个)
用时为下标为 i 1 i-1 1 的时间之和
②1 号回来,两个人一起去对岸,2 号回来以后再跟 1 号一起回去。
1 2(1 2 一起去对岸) 1(1 回来送氧气筒) i i-1(i 和 i-1 自生自灭一起渡河) 2(2 回来和 1 汇合准备下一次)
用时为下标为 2 1 i 2 的时间之和
所以记 t1=a[1]+a[2]+a[i-1]+a[i];t2=a[2]+a[1]+a[i]+a[2];
sum=sum+min(t1,t2);
接下来分奇偶讨论!
当渡河人数为偶数时,偶数 - 2 = 偶数
不妨设 n 恰好为 4 时,只需要渡河一次,
按照上诉 2 种方法,①可行,②扯淡,此时②必然会回到本岸,所以还要回去,sum=sum+a[2]
当渡河人数为奇数时,奇数 - 2 = 奇数
当 n 恰好为 3 时,就是 1 2 3 的渡河方法,最快的 1 3(1 3 去) 1(回来送氧气筒) 1 2(1 2 去)
时间是 3 1 2= a[1]+a[2]+a[3] sum=sum+a[1]+a[2]+a[3];
所以程序就非常简单:
- var t1,t2,n,sum,i:longint;
- a:array[1..1000]of longint;
- procedure qsort(l,r:longint);
- var t,i,j,mid:longint;
- begin
- i:=l; j:=r;
- mid:=a[(l+r)div 2];
- whileido
- begin
- whilea[i]do inc(i);
- whilea[j]>middo dec(j);
- ifi<=jthen begin
- t:=a[i]; a[i]:=a[j]; a[j]:=t;
- inc(i);dec(j);
- end;
- end;
- iflthen qsort(l,j);
- ifr>ithen qsort(i,r);
- end;
- begin
- assign(input,'river.in');
- assign(output,'river.out');
- reset(input);
- rewrite(output);
- readln(n);
- fori:=1 tondo read(a[i]);
- qsort(1,n);
- ifnmod 2=1 thensum:=a[1]+a[2]+a[3]
- elsesum:=a[2];
- i:=n;
- whilei>3 do begin
- t1:=a[2]+a[1]+a[i]+a[2];
- t2:=a[i]+a[1]+a[i-1]+a[1];
- ift1>t2thent1:=t2;
- sum:=sum+t1;
- i:=i-2;
- end;
- writeln(sum);
- close(input);
- close(output);
- end.
【贪心策略】渡河 (river)
来源: http://www.bubuko.com/infodetail-2093378.html