Autor: Piotrek (pgurgul_at_poczta.onet.pl)
Data: Mon 08 Dec 2003 - 18:53:53 MET
Witam,
postarałem sie skonstruowac rozwiazanie problemu optymalnego przydzialu
sal wykladowych, tak zeby wykorzystanych bylo jak najmniej. Czy moj algorytm
generuje optymalne wyniki? Ja mam watpliwosci, a ciezko mi powiedziec, gdyz
brak mi dosiwadczenia. Gdyby ktos mial ochote mi pomoc, bede wdzieczny.
oto kod:
#include <iostream.h>
long int P[100001];
long int K[100001];
long heap[100001];
void PushHeap(long int value, int &heapsize, long int heap[]);
void HeapIfy(long int heap[], int heapsize);
void quickSort(long int P[],long int K[], int pocz, int kon);
int partition(long int P[],long int K[], int pocz, int kon);
inline int parent(int i){
return i/2; }
inline int left(int i){
return 2*i;}
inline int right(int i){
return 2*i+1;}
main(){
int n; <--liczba wykladow
cin >> n;
for(int i=1; i<n+1; i++)
cin >> P[i] >> K[i]; <-- wczytywanie poczatkow i koncow wykladow
quickSort(P,K,1,n);
int heapsize=1;
heap[1]=K[1];
for(int i=2; i<n+1; i++)
if(P[i]<heap[1])
PushHeap(K[i], heapsize, heap);
else{
heap[1]=K[i];
HeapIfy(heap, heapsize);
}
cout << heapsize;
return 0;
}
int partition(long int P[],long int K[], int pocz, int kon){
long int x=P[(pocz+kon)/2];
int i=pocz-1;
int j=kon+1;
while(1){
do{j--;} while(P[j]>x);
do{i++;} while(P[i]<x);
if(i<j){
long int tmp=P[i];
P[i]=P[j];
P[j]=tmp;
tmp=K[i];
K[i]=K[j];
K[j]=tmp;
}
else
return j;
}
}
void quickSort(long int P[],long int K[], int pocz, int kon){
long int q=partition(P,K,pocz, kon);
if(pocz<q)
quickSort(P, K, pocz, q);
if(q+1<kon)
quickSort(P,K, q+1,kon);
}
void PushHeap(long int value, int &heapsize,long int heap[]){
++heapsize;
int i=heapsize;
while(i>1 && value<heap[parent(i)]){
heap[i]=heap[parent(i)];
i=parent(i);
heap[i]=value;
}
}
void HeapIfy(long int heap[], int heapsize){
long int value=heap[1];
int i=1, min=i;
while(1){
if(left(i)<=heapsize && heap[left(i)]<value)
min=left(i);
if(right(i)<=heapsize && heap[right(i)]<value && heap[right(i)]<heap[left
(i)])
min=right(i);
if(min!=i){
heap[i]=heap[min];
i=min;
}
else break;
heap[i]=value;
}
}
-- Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Wed 19 May 2004 - 11:52:57 MET DST