TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Stálý člen
Zdravim,
Na vstupe je prvy riadok pocet testov n (int) a nasledne 2n riadkov, pricom vzdy jeden test pozostava z dvoch riadkov - prvy pocet časov (int) a druhy časy (double).
Algoritmus prechadza vsetky casy a hlada hodinovy interval ktory pokryva najviac casov <cas,cas+1>. Po overeni vsetkych intervalov ten najlepsi vyhodi a analogicky opakuje az kym neurci vsetky intervaly pre vsetky casy.
Nebojte sa nechcem aby ste mi to nakodili :). Ide mi o to ze mam dva kody ktore robia presne to iste len jeden pouziva STL a jeho triedu list na ulozenie casov a s tym prisluchajuce operacie (sort,erase...). Druhy kod ukladay casy do pola a pouziva C-ckovsky qsort.
Problem je ze STL kod trva neporovnatelne (extremne) pomalsie ako ten druhy. Testovaci vstup ma 10 testov 10k,15k,20k,25k,30k,35k,40k,45k,50k,55k. Kod so standartnym polom zbehne cely za cca 20s a ten s STL len prvy test(10 000) trva 1m15s! Moja otazka a ziadost o radu na vas je preco je to tak, pripadne co tam mam zle, jednoducho pricina.
Dakujem!
STL code:
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
FILE *f = stdin;
void getIntervals();
int main()
{
int pocetTestov;
fscanf(f,"%d",&pocetTestov);
for(int j = 0;j<pocetTestov;j++)
{
getIntervals();
}
return 0;
}
void getIntervals()
{
int bestValue = 0;
int value = 0;
int pocetIntervalov = 0;
int pocetVlakov;
double time;
std::list<double>::iterator it;
std::list<double>::iterator current;
std::list<double>::iterator bestBegin;//potrebujeme kvoli vymazaniu najdeneho intervalu
std::list<double>::iterator bestEnd;//potrebujeme kvoli vymazaniu najdeneho intervalu
std::list<double> * pArriveTimes = new std::list<double>;
std::list<double> & arriveTimes = *pArriveTimes;
fscanf(f,"%d",&pocetVlakov);
for(int i=0;i<pocetVlakov;i++)//nacitanie casov
{
fscanf(f,"%lf",&time);
arriveTimes.push_back(time);
}
arriveTimes.sort();//sortnutie
while(!arriveTimes.empty())//iterujeme az kym neziskame vsetky intervaly
{
value = bestValue = 0;
current = arriveTimes.begin();//nastavime sa na zaciatok
while(current != arriveTimes.end())//iterujeme pokial nie sme na konci listu casov
{
time = *current;
for(it = current;it != arriveTimes.end();it++)//spocitame kolko casov zahrnuje interval
{
if(*it>=time+1.0)
break;
value++;
}
if(value>bestValue)//je pocet zahrnutych casov vacsi ako zatial najvacsi?
{
bestValue = value;
bestBegin = current;//aby sme vedeli na konci interval vymazat
bestEnd = it;//aby sme vedeli na konci interval vymazat
}
value = 0;
current++;//ideme skusat dalsi interval
}
pocetIntervalov++;
arriveTimes.erase(bestBegin,bestEnd);// vymazanie intervalu z listu casov
}
printf("%d\n", pocetIntervalov);
}
Basic code:
#include <stdio.h>
#include <stdlib.h>
int compare (const void * a, const void * b) // funkcia na porovnanie pre kniznicnu funkciu Quicksort
{
if (*(double*)a > *(double*)b)
return 1;
if (*(double*)a < *(double*)b)
return -1;
if (*(double*)a == *(double*)b)
return 0;
}
int main ()
{
int n,i,j,t,test,x,akt,pocetvintervale,najporadie,najpocetnejsi,zamestnanci;
double *pole;
double konint;
scanf("%d", &test);
for(t=1;t<=test;t++){ //zaciatok cyklu testov
scanf("%d", &n);
pole = (double *) malloc(n * sizeof(double));
for (i=0; i<n;i++){ // nacitanie pola
scanf("%lf", pole+i);
}
qsort (pole, n, sizeof(double), compare); // usporiadanie pola
zamestnanci = 0;
while(n!=0){
n = n-1;
najpocetnejsi = 0;
for(j=0;j<=n;j++){ // cyklus na prejdenie vsetkych prvkov pola
akt = j;
konint = pole[akt]+1;
pocetvintervale=0;
while(akt<=n && pole[akt]<=konint+0.000001){ // pocitanie pocetnosti intervalov pre konkretnu poziciu
akt++;
pocetvintervale++;
}
if (pocetvintervale>najpocetnejsi){ // zapamatanie najpocetnejsieho intervalu, pozicie a poctu
najpocetnejsi=pocetvintervale;
najporadie = j;
}
}
while(najporadie<=n-najpocetnejsi){ //skratenie pola o pocet prvkov najpocetnejsieho intervalu
pole[najporadie] = pole[najporadie+najpocetnejsi]; //od zaciatku miesta najdeneho intervalu postupne umiestnujeme hodnoty za intervalom, cim ho prekryjeme
najporadie++;
}
n=n-najpocetnejsi+1;
zamestnanci++;
}
printf("%d\n", zamestnanci);
free(pole);
}
return 0;
}
Nahlásit jako SPAM
IP: 188.121.172.–
God of flame
Grafoman
Posthunter
Zjistit počet nových příspěvků
