Текущ брой на Списание ИнфоМан
 


Февруарско състезание на 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