| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
蒟蒻的AC纪念//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator