> 有人能给一下accept的原代码吗，十分感谢！
枚举width的下界，每次贪心计算最优，然后求得到全局最优
AC code
应该还可以优化。
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int width[10000];
int top;

struct man
{
	int price,width;
};

struct node
{
	man value;
	node* next;
	node():next(NULL){};
};

node *head[100];
void init()
{
	int i;
	for(i=0;i<100;i++)
	{
		head[i]=new node();
	}
}

void clear(int n)
{
	node* dp;
	int i;
	for(i=0;i<n;i++)
	{
		dp=head[i]->next;
		while(dp!=NULL)
		{
			head[i]->next=dp->next;
			delete dp;
			dp=head[i]->next;
		}
	}
}



inline int cmp(const man& m1,const man& m2)
{
	if(m1.price<=m2.price&&m1.width>=m2.width)
		return 1;
	if(m2.price<=m1.price&&m2.width>=m1.width)
		return -1;
	return 0;
}

inline bool cmp1(const man& m1,const man& m2)
{
	return m1.width*m2.price>m1.price*m2.width;
}

bool cmp2(int a,int b)
{
	return a>b;
}


void insert(const man& in,int index)
{
	node *sp,*pre;
	int c;
	bool inser=true;
	pre=head[index];
	sp=pre->next;
	while(sp!=NULL)
	{
		c=cmp(in,sp->value);
		if(c==1)
		{
			pre->next=sp->next;
			delete sp;
			sp=pre->next;
		}
		else if(c==-1)
		{
			inser=false;
			break;
		}
		else
		{
			pre=sp;
			sp=sp->next;
		}
	}
	if(inser)
	{
		sp=head[index]->next;
		pre=head[index];
		while(sp!=NULL&&sp->value.price<in.price)
		{
			pre=sp;
			sp=pre->next;
		}
		pre->next=new node();
		pre=pre->next;
		pre->value.price=in.price;
		pre->value.width=in.width;
		pre->next=sp;
	}
}



int read(int n)
{
	int i,j,m;
	int maxrow,minmaxrow=0x7fffffff;
	man readin;
	top=0;
	for(i=0;i<n;i++)
	{
		cin>>m;
		maxrow=0;
		for(j=0;j<m;j++)
		{
			cin>>readin.width>>readin.price;
			width[top++]=readin.width;
			maxrow=max(readin.width,maxrow);
			insert(readin,i);
		}
		minmaxrow=min(minmaxrow,maxrow);
	}
	sort(width,width+top,cmp2);
	return minmaxrow;
}


int findminprice(int index,int boundwidth)
{
	node* sp=head[index]->next;
	while(sp->value.width<boundwidth)
	{
		sp=sp->next;
	}
	return sp->value.price;
}


int findmax(int boundwidth,int n)
{
	int allprice=0;
	int i;
	for(i=0;i<n;i++)
	{
		allprice+=findminprice(i,boundwidth);
	}
	return allprice;
}

int main()
{
	int test,n,boundw,nextindex;
	man currentman,minman;
	cin>>test;
	init();
	while(test>0)
	{
		test--;
		cin>>n;
		boundw=read(n);
		minman.width=boundw;
		minman.price=findmax(boundw,n);
		nextindex=0;
		while(width[nextindex]!=boundw)
			nextindex++;
		while(nextindex<top&&width[nextindex]==boundw)
			nextindex++;
		while(nextindex<top)
		{
			boundw=width[nextindex];
			currentman.width=boundw;
			currentman.price=findmax(boundw,n);
			if(cmp1(currentman,minman))
			{
				minman.price=currentman.price;
				minman.width=currentman.width;
			}
			while(nextindex<top&&width[nextindex]==boundw)
				nextindex++;
		}
		clear(n);
		cout<<fixed<<setprecision(3)<<(double)minman.width/(double)minman.price<<endl;
	}
	return 0;
}

• .......这么长？。。。 (14) yescrystal 2006-08-17 01:50:51
  • Re:.......这么长？。。。 (8) y05hcy 2006-10-06 15:02:34
    • Re:.......这么长？。。。 (169) 006794 2006-10-06 19:14:21
      • Re:.......这么长？。。。 (185) scu_try 2006-10-10 15:38:41
• 建议以后发到个人邮箱里,不要贴出来... (3454) xiedi 2006-10-06 21:02:25