Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

蒟蒻的AC纪念

Posted by CrystalBall at 2016-10-07 13:08:27 on Problem 1018
//784K   63ms
//大致思路是
//在每个种类中,由小到大枚举最小带宽,然后由大到小遍历出最小价格和。
//枚举最小带宽时,若出现无法满足每个种类都选择的情况,则跳到下一个种类枚举。遍历时若当前设备带宽小于最小带宽,则同样跳到下个种类。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctype.h>
using namespace std;

const int MAXDEVICE = 10000;
const int MAXN = 100;

struct node{
	int wid;
	int pri;
	int id;
}device[MAXDEVICE+1];

bool _cmp(node x, node y)
{
	if (x.id != y.id)
		return x.id < y.id;
	else if (x.wid != y.wid)
		return x.wid > y.wid;
	else
		return x.pri < y.pri;
}

int skip_white()
{
	int c;
	while ( (c=getchar()) != EOF && c==' ')
		c = getchar();
	return c;
}
void Myscan(int *n)
{
	int c;
	int last = skip_white();
	*n = (isdigit(last)) ? last-'0' : 0; 
	while ( (c=getchar()) != EOF && isdigit(c))
		*n = *n * 10 + c - '0';
}
int main()
{
	int t;
	int n;
	int mi;
	int i, j;
	int id;
	int conwid;
	int minofmax;
	int mark = 0;
	int conpri = 0;
	int totpri = 0;
	int count = 0;
	float temp;
	float ans = 0.0;
	int jump[MAXN+1];
	
	Myscan(&t);
	while (t--)
	{
		memset(device, 0, sizeof(device));
		memset(jump, 0, sizeof(jump));
		ans= 0.0;
		count = 0;

		Myscan(&n);
		
		for (i = 1; i <= n; i++)
		{
			Myscan(&mi);
			for (j = 1; j <= mi ;j++)
			{
				++count;
				Myscan(&device[count].wid);
				Myscan(&device[count].pri);
				device[count].id = i;
			}
		}
		sort(device+1, device+count+1,_cmp);
		
		mark = 0;
		for (i = 1; i <= count; i++)
		{
			id = device[i].id;
			if (id > mark)
			{
				jump[id] = i;
				mark++;
			}
		}
		for (i = count; i >= 1; i--)
		{
			id = device[i].id;
			conwid = device[i].wid;
			conpri = 0;
			totpri = 0;
			mark = 0;
			for (j = 1; j <= count; j++)
			{	
				if (device[j].wid < conwid)
				{
					if (device[j].id == mark)
						{
							j = jump[mark+1] - 1; 
							continue;
						}	
					else 
						break;
				}
				else
				{
					if (device[j].id == mark)
						conpri = (device[j].pri < conpri) ? device[j].pri : conpri;
					else
					{
						mark++;
						totpri += conpri;
						conpri = device[j].pri;
					}
				}
			}
			if (mark == n)
			{
				totpri += conpri;
				temp = (float)conwid/(float)totpri;
				ans = (temp > ans) ? temp : ans;
			}
			else 
				i = jump[id] ;
		}
		printf("%.3f\n",ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator