Февруарско състезание на USACO, 2005, Задача GOLD3. Aggressive cows
Условието на задачата може да прочетете
тук.
Решение
Задачата се свежда до това да намерим с какво е
максималното разлика между всеки два елемента в дадено подмножествоQ с Cелемента на дадено начално
множество P с N елемента.
Ще покажем как с линейно по Nвреме можем да проверим съществуването
на подмножество с Cелемента, минимално разстояние между
елементите на което е Т или повече. За целта сортираме масива с елементите на
началното множество в нарастващ ред. Избираме първия елемент от P за първи и в Qи обхождаме елементите на Pпоследователно и щом намерим такъв
който да е по – голям от последния добавен елемент е Qс Т или повече, то елементът от Pстава нов последен в Q. Продължаваме така докато или не
напълним Qс Cелемента, или не ни свършат
елементите в P. Ако сме успели да поставим Cелемента в Q,то значи сме намерили и съществува такова множество с Cелемента, с разлика на които и да е
два елемента поне Т. Забележете, че за
намереното множество може също да се каже, че разликата на които и да е два
елемента е поне L,където L<=T. Тоест ако намерим решение с минимална разлика поне Т
то няма нужда да търсим решения (и задължително съществуват) решения за всяко
естествено число по-малко от Т.
След като разполагаме с начин бързо (линейно) да
проверим съществуването на решение с минимална разлика поне Т, можем да приложим метода на двоичното
търсене. Ще търсим решение в интервала [l,r],където l<=r(в началото l=0, r = 1 000 000 000). Щом изберем средното число в интервала – mid, пробваме да конструираме множествоQ, разликата на които и два елементите
на което да е поне mid. Ако намерим такова, то
търсенето трябва да продължи в интервала [mid+1,r], а в противен случай в
интервала [l,mid-1].
Примерна реализация:
/*
PROG:aggr
LANG:C++
Nikola Borisof
*/
# include <stdio.h>
# include <stdlib.h>
# define MAXN 100005
int d[MAXN];
int n,c,best;
int cmp(const void *e1, const void *e2) {
return *(int *)e1-*(int *)e2;
}
void readf() {
// четене на входа
freopen("aggr.in","r",stdin);
freopen("aggr.out","w",stdout);
scanf("%d %d",&n,&c);
for ( int i=0 ; i<n ; i++ ) {
scanf("%d",d+i);
}
// сортираме входните данни
qsort(d,n,sizeof(int),cmp);
}
// тази функция проверява съществуването
// на решение с разлика между елементите поне p
// 1 - ако съществува 0 - иначе
int check(int p) {
int br = c-1, lpos = d[0];
for ( int i=1 ; i<n ; i++ ) {
if ( d[i]-lpos>=p ) {
br--;
lpos = d[i];
}
}
if ( br<=0 ) return 1;
return 0;
}
// двойчно търсене
void solve() {
int l, r, mid;
l = 0; r = 1000000000;
while ( l<=r ) {
mid = (r+l)/2;
if ( check(mid) ) {
best = mid;
l = mid+1;
} else {
r = mid-1;
}
}
}
int main() {
readf();
solve();
printf("%d\n",best);
return 0;
}
Автор: Никола Борисов
обратно към брой 27
|