---
# System prepended metadata

title: d872 過橋問題

---

# d872 過橋問題
## [題目連結](https://zerojudge.tw/ShowProblem?problemid=d872)
## 解題想法
* 依速度排序後，分為a(最快的帶所有人過去)、b(最快的兩個先去，再讓最慢的兩個過去)，從這兩個找出較快的方法
## 遭遇到的困難
* 最快的方式中間可能參雜兩種，不一定只用一種
* 要考慮人數為0或1的狀況
## 程式碼
```cpp=01
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int n,i;
	while(scanf("%d",&n)!=EOF){
		if(n==0)printf("0\n");
		else{
			int p[n];
			for(i=0;i<n;i++)scanf("%d",&p[i]);
			sort(p,p+n);
			int a=0,b=0,ans=0;
			while(n>=4){
				a=p[n-1]+p[0]+p[n-2]+p[0];
				b=p[1]+p[0]+p[n-1]+p[1];
				n-=2;
				if(a>=b)ans+=b;
				else ans+=a;
			}
			if(n==1)ans+=p[0];
			else if(n==2)ans+=p[1];
			else if(n==3)ans+=p[2]+p[0]+p[1];
			printf("%d\n",ans);
		}
	}
	return 0;
}