Балканска олимпиада по информатика 2005, Задача 1.2. REQUESTS
Уловието на задачата може да прочетете
тук.
Решение
Нека на
дадена стъпка трябва да се извади елемент от кутията. Разглеждаме
две ситуации:
1) В кутията
има елемент X, за който времето на
валидност ще е изтекло преди следващата заявка за обновяване за този предмет
иливъобще няма
такава следваща. В този случай най-оптимално е да се извади именно този обект
X, за да се освободи място за новия. Това
е така,
защото за този обект е ясно, че следващата заявка за него ще струва 1, независимо дали даденият обект е в
кутията или не. Ако следваща заявка няма, то ситуацията е подобна – независимо
дали обектът е в кутията или не, за него няма да се плаща повече.
2) В случай,
че няма такъв обект,се
изважда този обект от кутията, за който следващата заявка е най-далеч в
бъдещето. Това се прави, защото обектите, които ще бъдат обновени по-скоро,
имат по-голям шанс да останат в кутията до момента на тяхното следващо
обновяване, при което няма да се заплаща нищо.
Следвайки
тази логика се получава оптимално поставяне и вадене на обекти от кутията
спрямо зададените заявки.
Интересна
подробност за самите тестове от състезанието е, че при тях се приема, че
моментите започват от нулевия, докато в условието е поставено изискване да се
започва от първи.
Примерна реализация
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[1024],b[1024];
int list[128],d[128];
int used[128];
int n,k,res;
int main ()
{
int i,j,t,cnt,last;
freopen("requests.in","r",stdin);
freopen("requests.out","w",stdout);
scanf("%d%d",&k,&n);
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
//b[i]++;
}
cnt=0;
for (i=1;i<=n;i++)
if (cnt==k)
{
// check if we have the element in the box
for (j=1;j<=k;j++)
if (list[j]==a[i])
break;
if (j<=k)
{
if (d[j]<i) res++;
list[j]=a[i];
d[j]=b[i];
continue;
}
// remove invalid element
for (j=1;j<=k;j++)
if (d[j]<i)
break;
if (j<=k)
{
res++;
list[j]=a[i];
d[j]=b[i];
continue;
}
// remove the farthest element or that which will expire
res++;
last=-1;
memset(used,0,sizeof(used));
for (t=i+1;t<=n;t++)
{
for (j=1;j<=k;j++)
if (d[j]>=t && list[j]==a[t] && used[j]==0) break;
if (j<=k)
{
used[j]=1;
last=j;
}
}
for (j=1;j<=k;j++)
if (used[j]==0) break;
if (j>k) j=last;
list[j]=a[i];
d[j]=b[i];
}
else
{
for (j=1;j<=cnt;j++)
if (list[j]==a[i])
break;
if (j>cnt) cnt++;
if (d[j]<i) res++;
list[j]=a[i];
d[j]=b[i];
}
printf("%d\n",res);
return 0;
}
Автор: Ростислав Руменов
обратно към брой 27
|