SPOJ Problema com performance - problema 3775[resolvido]

1 resposta
denisspitfire

Pessoal, estou tentando resolver este problema, e deu tempo de execução a mais do que esperado. ò.ó.
Alguem poderia me ajudar? nao sei resolver os problemas com buffer ou inputstream…qual seria mais rapido? Alguem sabe um software de teste automatizado que seja bom?

import java.util.*;

class fliperama {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int rank, jogadas, cont;
		int vet[] = new int[1000];
		jogadas = scan.nextInt();
		rank = scan.nextInt();
		cont = 0;
		while (jogadas > 0) {
			vet[cont] = scan.nextInt();
			cont++;
			jogadas--;
		}
		quick_sort(vet, 0, 0);
		cont = 0;
		while (cont < rank) {
			System.out.println(vet[cont]);
			cont++;
		}

	}

	public static void quick_sort(int[] v, int ini, int fim) {
		int meio;

		if (ini < fim) {
			meio = partition(v, ini, fim);
			quick_sort(v, ini, meio);
			quick_sort(v, meio + 1, fim);
		}
	}

	public static int partition(int[] v, int ini, int fim) {
		int pivo, topo, i;
		pivo = v[ini];
		topo = ini;

		for (i = ini + 1; i < fim; i++) {
			if (v[i] < pivo) {
				v[topo] = v[i];
				v[i] = v[topo + 1];
				topo++;
			}
		}
		v[topo] = pivo;
		return topo;
	}

}

Desde já agradeço. VLW

1 Resposta

denisspitfire

Segue o código que passou no tempo…

import java.util.*;

class fliperama {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int rank, jogadas, cont,vetor;
		int vet[] = new int[10000];
		vetor=jogadas = scan.nextInt();
		rank = scan.nextInt();
		cont = 0;
		while (jogadas > 0) {
			vet[cont] = scan.nextInt();
			cont++;
			jogadas--;
		}
		quick_sort(vet, 0, vetor);
		cont = 0;
		while (cont < rank) {
			System.out.println(vet[cont]);
			cont++;
		}
	}

	public static void quick_sort(int[] v, int ini, int fim) {
		int meio;

		if (ini < fim) {
			meio = partition(v, ini, fim);
			quick_sort(v, ini, meio);
			quick_sort(v, meio + 1, fim);
		}
	}

	public static int partition(int[] v, int ini, int fim) {
		int pivo, topo, i;
		pivo = v[ini];
		topo = ini;

		for (i = ini + 1; i < fim; i++) {
			if (v[i] > pivo) {
				v[topo] = v[i];
				v[i] = v[topo + 1];
				topo++;
			}
		}
		v[topo] = pivo;
		return topo;
	}

}

Programei para que o quick nao ordenar todo o vetor… só oque era preciso.
a unica coisa que eu achei estranho… é que eu tinha errado o tamanho do vetor… e de 1000 era 10000 O.o?
estranho? que nada! rs
(pergunta… se o vetor era menor antes… pq deu tempo de execução? nao seria erro de compilação?)

Criado 9 de setembro de 2011
Ultima resposta 9 de set. de 2011
Respostas 1
Participantes 1