4860366_ac_16ms_296k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 32 行

#include<iostream>
using namespace std;
int time[1010];
int n;
int compare(const void*p1,const void*p2)
{
	return *(int*)p1-*(int*)p2;
}
int cross(int n)
{
	if(n==1) return time[0];
	if(n==2) return time[1];
	if(n==3) return time[0]+time[1]+time[2];
	int t1=time[n-1]+time[0]+time[n-2]+time[0];
	int t2=time[n-1]+time[1]+time[1]+time[0];
	if(t1<=t2)	return time[n-1]+time[0]+cross(n-1);
	else return t2+cross(n-2);
}
int main()
{
	int testnumber;
	cin>>testnumber;
	int i;
	for(int count=0;count<testnumber;count++)
	{
		cin>>n;
		for(i=0;i<n;i++) cin>>time[i];
		qsort(time,n,sizeof(int),compare);
		cout<<cross(n)<<endl;
	}
	return 0;
}