Отримання знань

дистанційна підтримка освіти школярів


Система коммуникаций
http://acm.pku.edu.cn/JudgeOnline/problem?id=1018

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < stdio.h >
#include < string.h >
#define MAXN 10010

int f[2][MAXN];
int dev[MAXN];
int task;
int n,m,t;

int main()
{
int i,j,k,l,p,q;
float h;
scanf("%d",&task);
while (task--)
{
scanf("%d",&n);
memset(f,-1,sizeof(f));
dev[0] = 2147473647;
f[0][0] = 0; t = 0;
for (i = 1; i <= n; i++)
{
scanf("%d",&m);
p = t;
for (j = 1; j <= m; j++)
{
t++;
scanf("%d%d",&dev[t],&k);
for (l = 0; l <= p; l++)
{
if (f[0][l] == -1) continue;
if (dev[l] > dev[t]) q = t;
else q = l;
if (f[0][l] + k < f[1][q] || f[1][q] == -1)
f[1][q] = f[0][l] + k;
}
}
memcpy(f[0],f[1],sizeof(f[0]));
memset(f[1],-1,sizeof(f[1]));
}
h = 0;
for (i = 0; i <= t; i++)
if (f[0][i] > -1)
if ((float)dev[i] / (float)f[0][i] > h)
h = (float)dev[i] / (float)f[0][i];
printf("%.3f\n",h);
}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)