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


USACO квалификационен кръг - октомври, GOLD Division, Задача flight

Уловието на задачата може да прочетете тук.

Решение

Тази задача може да се раздели на две идентични подзадачи. Нека разделим заявките за пътуване на две множества. Първите са такива, които искат да пътуват в посока от първия град към втория. Второто множество са заявки за пътуване в обратната посока. Трябва да се реши една и съща задача в двете посоки.

Всяка заявка има ляв и десен край – там, откъдето се тръгва, и там, където се отива. Нека се разгледат заявките в ред на нарастващ десен край. Когато дойде редът на една заявка, всички преди нея са изпълнени по някакъв начин. Това означава, че някои (в частност нула) от кравите от всяка заявка са били качени на самолета. Настоящата заявка A покрива интервала [x,y]. Трябва да се определи колко е най-голямата натовареност на самолета в [x,y]. Това може да се направи с помощта на индексно дърво. Неговата структура ще бъде описана по-долу. Като се намери тази стойност от дадената заявка A се вземат на самолета толкова крави, колкото може да побере самолетът в този най-натоварен момент. Това се прави за всички заявки в реда на нарастващ десен край. Същият подход се прилага и за заявките от второто множество.

Индексното дърво, което се използва в решението на тази задача дава информация за това колко е най-голямата натовареност на самолета в даден интервал. В това дърво всеки връх отговаря за даден интервал [x,y]. Неговите наследници отговарят за двете половини на интервала. Същото се отнася и за наследниците надолу. Ако търсения интервал има общи точки с интервала на левия наследник на корена се прави запитване за левия наследник. Ако има общи точки и с интервала на десния наследник се пита и за десния наследник. Взема се по-голямата от двете стойности за неговите наследници и това е отговора за дадения интервал. Така рекурсивно може да се пресметне стойността за даден връх в дървото. Когато се прави заявка за даден интервал се започва претърсването на дървото от корена. Същото се прави за всеки връх, за който има запитване.

Сложността на едно запитване или на дабавяне на стойност в дървото е O(logN).

Сложността на това решение е O(K*logN)тъй като за всяко пътуване се прави запитване към дървото и добавяне на стойност в него.

Примерна реализация


# include <cstdio>
# include <cstdlib>
# include <algorithm>
# include <vector>
# define MAXN (1<<16)
# define MAXT (1<<14)
# define min(a,b) (((a)<(b))? (a):(b))
# define max(a,b) (((a)>(b))? (a):(b))
using namespace std;

struct group{
	//from, to, number of cows, junk element for faster indexation
    int f,t,num,junk;
    group() { f=0,t=0,num=0;}
    group(int a, int b, int c) { f=a, t=b, num=c; }
};
struct node{
    int maxch, st;
};
vector <group> data1;
vector <group> data2;
int n,k,cap,sum;

node t[MAXT*2];

class Comp {
    public:
    	bool operator()(const group a, const group b) const {
    	    return a.t < b.t;
	}
};

class Comp1 {
    public:
	bool operator()(const group a, const group b) const {
	    return a.t > b.t;
	}
};


// Reading Input
void readf() {
    freopen("flight.in","r",stdin);
    freopen("flight.out","w",stdout);
    scanf("%d %d %d",&k,&n,&cap);
    group buf;
	// Separate the groups
    for ( int i=0 ; i<k ; i++ ) {
		scanf("%d %d %d",&buf.f,&buf.t,&buf.num);
		if ( buf.f<buf.t ) {
		    data1.push_back(buf);
		} else {
			data2.push_back(buf);
		}	
    }
	// Sort by end
    sort(data1.begin(),data1.end(),Comp());
    sort(data2.begin(),data2.end(),Comp1());
}

/* Index tree for intervals (Mars like) */
//***************************************************8
//Ask function
int ask(int x, int y, int p, int l, int r) {
    int mid = (l+r)/2,a,b;
    if ( x==l && y==r ) return t[p].maxch+t[p].st;
    if ( y<=mid ) {
		a = ask(x,y,2*p+1,l,mid);
		return a+t[p].st;
    }
    if ( x>mid ) {
		a = ask(x,y,2*p+2,mid+1,r);
		return a+t[p].st;
    }
    a = ask(x,mid,2*p+1,l,mid);
    b = ask(mid+1,y,2*p+2,mid+1,r);
    return max(a,b)+t[p].st;
}

//***************************************************8
//Update function
void update(int x, int y, int p, int l, int r, int st) {
    int mid = (l+r)/2;
    if ( x==l && y==r ) {
		t[p].st+=st;
		return;
    }
    if ( y<=mid ) {
		update(x,y,2*p+1,l,mid,st);
		t[p].maxch = max(t[p].maxch,t[2*p+1].maxch+t[2*p+1].st);
		return;
    }
    if ( x>mid ) {
		update(x,y,2*p+2,mid+1,r,st);
		t[p].maxch = max(t[p].maxch,t[2*p+2].maxch+t[2*p+2].st);
		return;
    }
    update(x,mid,2*p+1,l,mid,st);
    t[p].maxch = max(t[p].maxch,t[2*p+1].maxch+t[2*p+1].st);
    update(mid+1,y,2*p+2,mid+1,r,st);
    t[p].maxch = max(t[p].maxch,t[2*p+2].maxch+t[2*p+2].st);
}

//***************************************************

void solve(bool p) {
    int x;
    if ( p==0 ) {
		for ( int i=0 ; i<(signed)data1.size() ; i++ ) {
    		x = ask(data1[i].f,data1[i].t-1,0,0,MAXT-1);
			if ( x<cap ) {
				sum+=min(cap-x,data1[i].num);
				update(data1[i].f,data1[i].t-1,0,0,
				       MAXT-1,min(cap-x,data1[i].num));
			}
		}
    } else {

		for ( int i=0 ; i<(signed)data2.size() ; i++ ) {
//			printf("%d %d %d\n",data2[i].f,
                   data2[i].t,data2[i].num);
			x = ask(data2[i].t+1,data2[i].f,0,0,MAXT-1);
			if ( x<cap ) {
				sum+=min(cap-x,data2[i].num);
				update(data2[i].t+1,data2[i].f,0,0,
				       MAXT-1,min(cap-x,data2[i].num));
			}
		}
    }    
}

void init() {
    for ( int i=0 ; i<MAXT*2 ; i++ ) {
	t[i].maxch = 0; t[i].st = 0;
    }
}

int main() {
    readf();
	//Solve from North to South
    solve(0);
    init();
	//Solve from South to North
    solve(1);
    printf("%d\n",sum);

    return 0;
}




Автор: Никола Борисов


обратно към текущ брой