1700.cpp

来自「北大acm的部分题目答案。绝少水题。均是本人自行求解并通过。」· C++ 代码 · 共 79 行

#include<iostream>
using namespace std;

int partition(int *base,int low,int high)
{
	base[0]=base[low];
	while(low<high)
	{
		while(low<high&&base[high]>=base[0])high--;
		base[low]=base[high];
		while(low<high&&base[low]<=base[0])low++;
		base[high]=base[low];
	}
	base[low]=base[0];
	return low;
}


void QSort(int *base,int low,int high)
{
	int m;
	if(low<high)
	{
	m=partition(base,low,high);
	QSort(base,low,m-1);
	QSort(base,m+1,high);
	}
}

void QuickSort(int*base,int n)
{
	QSort(base,1,n);
}
//从1开始计数

int count(int *a,int n)
{
	//n个人，每个人的渡河时间数组time已经从小到大排好序
	if(n==1)return a[1];
	int i,sum=0;
	if(n%2==0)
	{
		for(i=n;i>=4;i-=2)
			if(2*a[2]+a[1]<2*a[1]+a[i-1])sum+=a[i]+2*a[2]+a[1];
			else sum+=a[i]+a[i-1]+2*a[1];
		    sum+=a[2];
	}
	if(n%2)
	{
		for(i=n;i>=5;i-=2)
		if(2*a[2]+a[1]<2*a[1]+a[i-1])sum+=a[i]+2*a[2]+a[1];
	    else sum+=a[i]+a[i-1]+2*a[1];
		sum+=a[3]+a[2]+a[1];
	}
	return sum;
}

//从1开始计数
int main()
{
	int k,t,n,i,time[1002],an;
	cin>>t;
	for(k=1;k<=t;k++)
	{
		cin>>n;
		for(i=1;i<=n;i++)
			cin>>time[i];
		QuickSort(time,n); 
		an=count(time,n);
		cout<<an<<endl;
	}
	return 0;
}