n人最速ブリッジ問題【java版】

【問題の説明】
n人は夜に橋を渡り、いつでも2人で1組で橋を渡り、各組に懐中電灯を1本持たなければならない.このn人の中で1つの懐中電灯しか使えないので、ある往復で懐中電灯を返却し、より多くの人が橋を渡ることができるように手配します.
人によって橋を渡る速度が異なり、各グループの速度は橋を渡るのが最も遅い人が使う時間によって決定され、n<=1000と約束され、誰もいない橋を渡る時間は100秒を超える.
【入力】
入力された最初の行はnを与え、次のn行は1人当たりのブリッジ時間を与え、1000人を超えず、誰もいないブリッジ時間は100秒を超える.
1 2 5 10
【出力】
出力された最初の行は、すべてのn人がブリッジを通過する総秒数を与え、次のいくつかの行は、実装ポリシーを与える.各行には、1つまたは2つの整数が含まれ、ブリッジを構成する1人または2人が時間で識別されることを示します.全部で:17秒で行く:1 2回:1行く:5 10回:2行く:1 2
【分析】
1回のブリッジは最大2人であり、懐中電灯は往復伝達を必要とするため、2人のメンバーがブリッジを通過することを分析単位として、ブリッジ時間を計算する.n個のメンバーをブリッジ時間の増加順にソートします.a[1]は最も速い人であり、a[2]に次いで、a[n]は最も遅い人であり、a[n-1]は最後から2番目に遅い人である.相対的な状況では、次の2つのシナリオがあります.
◆方案一:最も速いメンバーa[1]で懐中電灯を伝達して最も遅いa[n]とa[n-1]が橋を渡るのを助け、往復にかかる時間が2*a[1]+a[n]+a[n-1]であることが分かりやすい
◆シナリオ2:最も速いメンバーa[1]と次の速いメンバーa[2]で懐中電灯を伝達して最も遅いa[n]とa[n-1]が橋を渡るのを助ける.具体的なシナリオは以下の通りである.
1.a[1]とa[2]から対岸までの時間はa[2]である.
2.a[1]は、最も遅いa[n]およびa[n−1]に懐中電灯を返し、a[n]およびa[n−1]は対岸に着いた後、a[2]に懐中電灯を渡し、かかる時間は、a[1]+a[n];
       3.a[2]は戻り、使用時間はa[2]である.
シナリオ2を統合するために用いられる総時間は2*a[2]+a[n]+a[1]である.
明らかに、2つのスキームの良し悪しは彼らの総時間に依存し、2 a[1]+a[n]+a[n-1]<2 a[2]+a[n]+a[1]、すなわち第1のスキームを採用し、そうでなければ第2のスキームを採用する.私たちは毎回最も遅い2人を助けて橋を渡って、時間を累積して、最後に現れる可能性のある2つの状況:
1.対岸には2人の隊員が残り、全員橋を渡り、時間はa[2].
2.対岸には3人の隊員が残っており、最も速いメンバーで懐中電灯を渡し、最も遅いメンバーが橋を渡るのを助け、次に遅いメンバーと一緒に橋を渡る.時間はa[1]+a[n-1]+a[n]である.
ここのn=3に注意してください.
コード#コード#

package test;

import java.util.Arrays;
import java.util.Scanner;

public class NMenCrossBridge {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n,i,k;//   n,i,j,k       ，        
        int[] a=new int [1024];
        int sum=0; //     
        n=sc.nextInt();
        //    
        for(i=1;i <= n;i++)
            a[i]=sc.nextInt();

        if(n == 1){
            System.out.format(a[1]+"%n"+a[1]);
        }

        k=n;
        while(k>3)	//    
        {
            if(a[1]+a[k-1] < 2*a[2])
                sum += a[k] + a[1]*2 + a[k-1];
            else
                sum += a[2]*2+ a[1] + a[k];
            k-=2;
        }
        if(k==2)	//        
            sum+=a[2];
        else		//    3   
            sum+=a[1]+a[2]+a[3];

        System.out.println(sum);//  n       
        k=n;
        while(k>3)	//      
        {
            if(a[1]+a[k-1]<2*a[2])	//   a[1]       
            {
                System.out.format(a[1]+" "+a[k]+"%n"+a[1]+"%n"+a[1]+" "+a[k-1]+"%n"+a[1]);
            }
            else					//   a[1]、a[2]         
            {
                System.out.format(a[1]+" "+a[2]+"%n"+a[1]+"%n"+a[k]+" "+a[k-1]+"%n"+a[2]+"%n");
                k-=2;
            }

            if(k==2)
                System.out.println(a[1]+" "+a[2]);
            else
                System.out.format(a[1]+" "+a[3]+"%n"+a[1]+"%n"+a[1]+" "+a[2]);

        }
    }

}

入力:
5 1 2 4 5 10
実行結果:
22 1 2 1 10 5 2 1 4 1 1 2