比赛 20091026 评测结果 C
题目名称 抗震救灾 最终得分 0
用户昵称 magic 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-10-26 21:42:59
显示代码纯文本
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
const int maxlong=10000000;
int a[10005],maxx=maxlong;
int b[10005];
int sum[10005];
string s[5005],ans;
void qsort(int l,int r);
void qsort(int l,int r)
{
	int i,j,x,y;
	string t;
	i=l;j=r;x=b[(l+r)/2];
	while (i<=j)
	{
		while (b[i]<x) i++;
		while (b[j]>x) j--;
		if (i<=j)
		{
			y=b[i];b[i]=b[j];b[j]=y;
			y=a[i];a[i]=a[j];a[j]=y;
			t=s[i];s[i]=s[j];s[j]=t;
			i++;j--;
		}
	}
	if (l<j) qsort(l,j);
	if (i<r) qsort(i,r);
}
int main()
{
	
	ifstream fi("saves.in");
	ofstream fo("saves.out");
	int p=1;
	while (!fi.eof())
	{
		fi>>a[p]>>b[p]>>s[p];
		p++;
	}
	qsort(1,p-1);
	for (int i=1;i<=p-1;i++)
	{
		int temp=0;
		for (int j=1;j<=p-1;j++)
		{
			if (i!=j)
			{
				temp+=abs(b[j]-b[i])*a[j];
			}
		}
		if (temp<maxx)
		{
			maxx=temp;
			ans=s[i];
		}
	}
	fo<<ans;
	return 0;
}