poj1700-Crossing River(貪心算法)，crossingriver
一，題意：
只有一艘船，能乘2人，船的運行時間為2人中較多一人的時間，過去後還需一個人把船劃回來，問把n個人運到對岸，最少需要多久。
二，思路步驟：
想辦法先把用時最多的2人，運過去，再把剩下來的人中用時最多的2人運過去，依次循環下去，直到n<=3。
1,n>3時：
①最快和次快過去,最快回;最慢和次慢過去,次快回,time=s[1]+s[0]+s[n-1]+s[1]。
②最快和最慢過去,最快回;最快和次快過去,最快回,time=s[n-1]+s[0]+s[n-2]+s[0]。
選擇兩者中用時較少的一個策略執行。如此便將最慢和次慢送過河，對剩下n-2個人循環處理
注意：當n=1、n=2、n=3時直接相加處理即可.
2,n==3時 ①= ②= time + s[0]+s[1]+s[2];
3,n==2時 time += s[1];
4,n==1時 time += s[0]。
![]()
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 int main(){
5 int t , n ;
6 int s[1005];
7 cin>>t;
8 while(t--){
9 cin>>n;
10 int time = 0;
11 for(int i = 0 ; i < n ; i++){
12 cin>>s[i];
13 }
14 while(n>3){ //當n>3時,重復方法選擇最小的用時相加
15 time = min(time + s[1]+s[0]+s[n-1]+s[1],time + s[n-1]+s[0]+s[n-2]+s[0]);
16 n-=2; //每次循壞過2個人
17 }
18 if(n==3)time += s[0]+s[1]+s[2];
19 else if(n==2)time += s[1];
20 else time += s[0];
21 cout<<time<<endl;
22 }
23 return 0;
24 }
View Code
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
