cqyz oj |ダイビング大会|貪欲



Cqyz Oj Diving Competition Greedy



説明

彼はマケドニアのオヒデ湖でダイビング大会を開催しました。プロジェクトの1つは、山から水に飛び込んで、最後までダイビングすることです。これはグループプロジェクトであり、n人の個人のチームです。酸素ボンベダイビングを使用する必要がありますが、各チームには酸素ボンベが1つしかありません。最大2人が酸素ボンベを使用しますが、今回はシンクロナイズドスイミングが必要なため、1回のランニングの終了までの時間は、終了に必要な時間と同じくらい遅くなります。幸いなことに、彼らはとてもフレンドリーなので、2人で一緒に泳ぐことをいとわない。最後のプレイヤーができるだけ早く最後に​​到達するように、水中戦略を調整します。

入力

1行目:単一の整数n、チームの数。次のn行。各行は、Ti(0)の終わりまでのi番目の個々の移動時間を表す整数です。<= n, Ti <= 1000).



出力

最初のチームの終わりに到達する時間。

サンプル入力1

3
1
3
4



サンプル入力2

6
1

5
6
8
9

サンプル出力1

8

サンプル出力2

27




この質問はイタリアを意味します:返送されたダイビングボトルに行くのは素晴らしかったです

最初の並べ替え
少なくとも4人の個人がいる場合、2種類が最適な欲張り戦略を取ります。
1、過去の輸送が最も遅い2人のうち、最も速い人が戻ってきます。処理済みT [n] + T [1] + T [n-1] + T [1]
2、そして最初の人よりも速い時間で、2人の中で最も遅い人を一緒に通り過ぎ、次にボトルを後ろに戻し、処理されたT [2] + T [2] + T [n] + T [1]

#include #include #include #include using namespace std typedef long long ll int a[1005],sum=0 int main(){ int n scanf('%d',&n) for(int i=1i=4){ sum+=min(a[1]*2+a[n]+a[n-1], a[2]*2+a[1]+a[n]) n-=2 } // less than four individual direct discussions if(n==3)sum+=a[1]+a[2]+a[3] else sum+=a[2]//n==2 printf('%d',sum) return 0 }