tape.cpp

设计一个算法

#include "iomanip"
#include "fstream"
#include "iostream"
using namespace std;
void Merge(double c[],double d[],int l,int m,int r)
{
	int i=l,j=m+1,k=l;
	while((i<=m)&&(j<=r))
		if(c[i]<=c[j]) 
			d[k++]=c[i++];
		else 
			d[k++]=c[j++];
		if(i>m)
			for(int q=j;q<=r;q++)
				d[k++]=c[q];
			else
				for(int q=i;q<=m;q++)
					d[k++]=c[q];
}
void MergePass(double x[],double y[],int s,int n)
{
	int i=0;
	while(i<=n-2*s)
	{
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	if(i+s<n)
		Merge(x,y,i,i+s-1,n-1);
	else
		for(int j=i;j<=n-1;j++)
			y[j]=x[j];
}

void MergeSort(double a[],int n)
{
	double *b=new double[n];
	int s=1;
	while(s<n)
	{
		MergePass(a,b,s,n);
		s+=s;
		MergePass(b,a,s,n);
		s+=s;
	}
}
int main()
{

	ifstream input("input.txt");
    ofstream output("output.txt"); 
	int n,i,j;
	double c[10000][2],a[10000],s=0,p=0;
	input>>n;
	for(i=0;i<n;i++)
		for(j=0;j<2;j++)
			input>>c[i][j];
		for(i=0;i<n;i++)
		{
			a[i]=c[i][0]*c[i][1];
			s+=c[i][1];
		}
		for(i=0;i<n;i++)
			a[i]/=s;
		MergeSort(a,n);
		for(i=1;i<n;i++)
			a[i]=a[i]+a[i-1];
		for(i=0;i<n;i++)
			p+=a[i];
		output<<p<<endl;
		return 0;
}