2291.cpp

北大acm的部分题目答案。绝少水题。均是本人自行求解并通过。

#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);
}


int max(int *a,int n)
{
	int i,max,sum;
	sum=max=a[n];
    for(i=n-1;i>=1;i--)
	{
		sum+=a[i];
		if(max<a[i]*(n-i+1))max=a[i]*(n-i+1);
	}
	return max;
}

int main()
{
	int k,i,t,n[11],a[1002],an[12];
    cin>>t;
	for(k=1;k<=t;k++)
	{
	cin>>n[k];
	for(i=1;i<=n[k];i++)
		cin>>a[i];
	QuickSort(a,n[k]);
	an[k]=max(a,n[k]);
	}
	for(k=1;k<=t;k++)
		cout<<an[k]<<endl;
	return 0;
}