Witam
poniższy kod zwraca "przekroczono limit czasu"
Dawniej, gdy pisałem w C++ tego typu błąd był rzadkością, stąd też moje pytanie, czy to zadanie da się w ogóle napisać w Javie czy może kod trzeba po prostu zoptymalizować?
EDIT: zamieszczam również link do tego samego kodu na pastebin, ponieważ wklejenie kodu tutaj najwyraźniej przerosło moje umiejętności: http://pastebin.com/nUXXVj0s
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static int liczbaTestow, poczLiczbaPlikow;
static int[] tablica;
static int sumaNajkrotszegoLaczenia;
static ArrayList<Plik> lista;
static LinkedList<Para> listaPar;
static Scanner input = new Scanner(System.in);
static Plik najmniejsza, drugaNajmniejsza;
public static void main(String[] args) {
int liczbaTestow = input.nextInt();
for (int i = 1; i <= liczbaTestow; ++i) {
poczLiczbaPlikow = input.nextInt();
lista = new ArrayList<Plik>();
listaPar = new LinkedList<Para>();
inicjalizujListe();
sumaNajkrotszegoLaczenia = 0;
while(lista.size()!=1) {
najmniejsza = znajdzNajmniejsza();
drugaNajmniejsza = znajdzDrugaNajmniejsza(najmniejsza);
sumaNajkrotszegoLaczenia += najmniejsza.dlugosc + drugaNajmniejsza.dlugosc;
usunElementOPozycji(najmniejsza.pozycja);
ustawDlugoscNaPozycji(drugaNajmniejsza.pozycja, drugaNajmniejsza.dlugosc + najmniejsza.dlugosc);
if(najmniejsza.pozycja < drugaNajmniejsza.pozycja) {
listaPar.add(new Para(najmniejsza.pozycja, drugaNajmniejsza.pozycja));
zmienNumerPozycji(drugaNajmniejsza.pozycja, najmniejsza.pozycja);
}
else
listaPar.add(new Para(drugaNajmniejsza.pozycja, najmniejsza.pozycja));
}
System.out.println(sumaNajkrotszegoLaczenia);
wypiszPary();
}
input.close();
}
static void inicjalizujListe() {
int iter = 0;
for (int i=0; i<poczLiczbaPlikow ; ++i) {
Plik p = new Plik();
p.pozycja = ++iter;
p.dlugosc = input.nextInt();
lista.add(p);
}
}
static Plik znajdzNajmniejsza() {
Plik najmniejsza;
najmniejsza = lista.get(0).kopiuj();
for (Plik p : lista)
if (p.dlugosc < najmniejsza.dlugosc) {
najmniejsza.pozycja = p.pozycja;
najmniejsza.dlugosc = p.dlugosc;
}
return najmniejsza;
}
static Plik znajdzDrugaNajmniejsza(Plik Najmniejsza) {
if (lista.size() <= 1)
return null;
else {
Plik drugaNajmniejsza;
if(Najmniejsza.pozycja != lista.get(0).pozycja) {
drugaNajmniejsza = lista.get(0).kopiuj();
}
else
drugaNajmniejsza = lista.get(1).kopiuj();
for(Plik p : lista) {
if(p.pozycja == Najmniejsza.pozycja)
continue;
if(p.dlugosc < drugaNajmniejsza.dlugosc) {
drugaNajmniejsza.pozycja = p.pozycja;
drugaNajmniejsza.dlugosc = p.dlugosc;
}
}
return drugaNajmniejsza;
}
}
static boolean usunElementOPozycji(int nrPozycji) {
for(Plik p : lista)
if(p.pozycja == nrPozycji)
return lista.remove(p);
return false;
}
static void zmienNumerPozycji(int staryNumer, int nowyNumer) {
for(Plik p :lista) {
if(p.pozycja == staryNumer)
p.pozycja = nowyNumer;
}
}
static void ustawDlugoscNaPozycji(int nrPozycji, int nowaDlugosc) {
for(Plik p :lista) {
if(p.pozycja == nrPozycji)
p.dlugosc = nowaDlugosc;
}
}
static void wypiszPary() {
for(Para p :listaPar) {
System.out.println(p.mala+" "+p.duza);
}
}
}
class Plik {
int dlugosc;
int pozycja;
Plik kopiuj() {
Plik kopia = new Plik();
kopia.dlugosc = this.dlugosc;
kopia.pozycja = this.pozycja;
return kopia;
}
}
class Para{
int mala;
int duza;
Para(int _mala, int _duza){
mala = _mala;
duza = _duza;
}
}
