import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.Vector;
/* les M titres de Wikipedia les plus longs
* utilisation :
* gzip -cd frwiki-... | java Wiki 5
*/
class Title implements Comparable
{
private String title;
Title(String title) {
this.title = title;
}
public int compareTo(Title that) {
return this.title.length() - that.title.length();
}
public String toString() { return this.title; }
}
// 1. solution vraiment naïve : lire tout le fichier et le trier
class Wiki0 {
public static void main(String[] args) throws IOException {
double start = System.currentTimeMillis();
int m = Integer.parseInt(args[0]);
System.out.print("reading... ");
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
Vector v = new Vector();
while (true) {
String s = r.readLine();
if (s == null) break;
v.add(new Title(s));
}
int n = v.size();
System.out.println(n + " titles");
System.out.print("sorting... ");
Collections.sort(v);
System.out.println("done");
for (int i = n-m; i < n; i++)
System.out.println(v.get(i));
System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
}
}
// 1. avec un tableau trié de taille M
class Wiki1 {
public static void main(String[] args) throws IOException {
double start = System.currentTimeMillis();
int m = Integer.parseInt(args[0]);
System.out.print("reading... ");
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
Title[] v = new Title[m];
int n = 0, total = 0;
while (true) {
String s = r.readLine();
if (s == null) break;
total++;
Title t = new Title(s);
int i = n;
while (i > 0 && v[i-1].compareTo(t) <= 0) {
if (i < m) v[i] = v[i-1];
i--;
}
if (i < m) v[i] = t;
if (n < m) n++;
}
System.out.println(total + " titles");
System.out.println("done");
for (int i = n-1; i >= 0; i--)
System.out.println(v[i]);
System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
}
}
// 2. solution efficace avec une file de priorité
class Wiki2 {
public static void main(String[] args) throws IOException {
double start = System.currentTimeMillis();
int m = Integer.parseInt(args[0]);
System.out.print("reading... ");
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue h = new PriorityQueue();
int n = 0;
while (true) {
String s = r.readLine();
if (s == null) break;
n++;
h.add(new Title(s));
if (h.size() > m) h.remove();
}
System.out.println(n + " titles");
while (h.size() > 0)
System.out.println(h.remove());
System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
}
}
// 3. solution avec un TreeSet (pour comparer)
// mais TreeSet n'admet pas de doublons => ne donne pas la bonne réponse
class Wiki3 {
public static void main(String[] args) throws IOException {
double start = System.currentTimeMillis();
int m = Integer.parseInt(args[0]);
System.out.print("reading... ");
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
TreeSet h = new TreeSet();
int n = 0;
while (true) {
String s = r.readLine();
if (s == null) break;
n++;
h.add(new Title(s));
if (h.size() > m) h.remove(h.first());
}
System.out.println(n + " titles");
for (Title t: h)
System.out.println(t.toString());
System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
}
}