Ciao a tutti!
Qualcuno ha dei consigli su come risolvere reading ?
Non passo i test non per colpa della complessità, che dovrebbe essere n lg(n), ma quasi sicuramente per come “estraggo” i testi con più pagine.
import java.util.*;
public class reading {
// max memory = 256 MiB = 268.435456 MB
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
final int NO_DEADLINE = -1;
// 1 ≤ N, L ≤ 150000.
int N = in.readInt(); // # papers
int L = in.readInt(); // # days
// < deadline, # pages > of papers WITH deadline
Map<Integer, Integer> withDlMap = new HashMap<>();
// max size of the Map = L
// < # pages > of papers WITHOUT deadline
LinkedList<Integer> withoutDlList = new LinkedList<>();
// max size of the LinkedList = N
for (int i = 0; i < N; i++) {
// 1 ≤ Pi ≤ 100 for each i = 0 . . . N − 1.
int Pi = in.readInt(); // # pages
// 0 ≤ Di < L − 1 or Di = −1 for each i = 0 . . . N − 1.
int Di = in.readInt(); // deadline
if (Di == NO_DEADLINE) {
withoutDlList.add(Pi);
} else {
withDlMap.merge(Di, Pi, Integer::max);
}
}
withoutDlList.addAll(withDlMap.values());
// decreasing ordering of the LinkedList
withoutDlList.sort(Collections.reverseOrder());
int result = 0;
int readable = Math.min(L,withoutDlList.size());
for (int i = 0; i < readable; i++) {
result += withoutDlList.get(i);
}
System.out.println(result);
}
}
sei sicuro che scegliere i primi L libri sia la scelta corretta?
prendiamo questo come esempio, ignorando il numero di pagine per il momento
3 1
1 1 1
hai 3 libri che puoi leggere fino al giorno 1, e il giorno 1 è l’ultimo giorno disponibile. secondo il tuo ragionamento dovremmo scegliere i primi L libri. L è uguale a 1, quindi prendiamo solo il primo libro. in realtà potresti leggerne 2, uno al giorno 0 e uno al giorno 1. inoltre come hai scritto salvi un libro che ha una scadenza solo se ha più pagine di uno con la stessa scadenza(se ho capito bene), e con l’esempio sopra ti porterebbe ad avere solo un libro da leggere.
inoltre da quel che ho capito ordini per il numero di pagine, ma questo non ti porta sempre alla risposta corretta
3 1
30 0
40 0
20 1
considerando l’esempio sopra, ipotizziamo che tu prenda i primi L+1 libri (dato che si parte dal giorno 0) che hanno più pagine, 70 sarebbe la risposta corretta? no, perché non puoi leggere due libri nel giorno 0,quindi la risposta corretta sarebbe 60
Al di là di evenutali problemi nella soluzione, il codice non sembra neppure compilare su training. (In particolare non riconosce la classe InputReader).
Sostituendo InputReader con Scanner il codice compila, ma ci mette 1.1 secondi solo a leggere l’input e fa TLE includendo anche la parte di risoluzione.
Questo non è un problema dovuto alla complessità della soluzione, solo al fatto che Java è un linguaggio intrinsecamente lento e pertanto poco adatto alla programmazione competitiva.
Ti consiglio, oltre a correggere la logica della tua soluzione, di riscriverla in C++: in Java rischi solo che una soluzione corretta non passi per la lentezza del linguaggio.
InputReader è una classe creata appunto per leggere più velocemente da stdin con java.
Ho dimenticato di copiarla nella soluzione.
La colpa del non riuscire a passare i test case, però non è però da cercarsi nella velocità con cui si legge l’input, ma nella logica del programma, in quanto con InputReader ottengo “output non corretto” e non TLE.
Questo caso non potrà verificarsi, se noti come aggiungo un valore alla mappa, mi assicuro che prima di salvarlo esso sia il maggiore, data la stessa chiave.
Quindi con l’input:
Avevo anche provato a ragionare in questo modo:
Gli unici paper su cui devo scegliere se tenere quelli con o senza scadenza sono i paper che sforano i L giorni.
Chiaramente il problema vuole massimizzare il numero di pagine, quindi dovrò eliminare i paper di una o dell’altra categoria che hanno meno pagine in assoluto.
Liberatomi dei paper in eccesso, facendo la somma delle pagine dei restanti dovrei ottenere la soluzione
//...................... fino a chiusura for
// ordering of the WITHOUT deadline LinkedList
Collections.sort(withoutDlList);
LinkedList<Integer> withDlList = new LinkedList<>(withDlMap.values());
Collections.sort(withDlList);
int daysOverlapping = 0;
if (withoutDlList.size() + withDlList.size() > L) {
daysOverlapping = withoutDlList.size() + withDlList.size() - L;
}
for (int day = 0; day < daysOverlapping; day++) {
if (withDlList.getFirst() <= withoutDlList.getFirst()) {
withDlList.removeFirst();
} else{
withoutDlList.removeFirst();
}
}
int result = 0;
for (Integer item : withoutDlList) {
result += item;
}
for (Integer item : withDlList) {
result += item;
}
System.out.println(result);
è possibile vedere questa classe? Comunque è un consiglio generale quello di non usare Java: la differenza rispetto a C++ è considerevole ed è praticamente garantito che far passare soluzioni in Java si debba fare lavoro extra (tipo scrivere classi specifiche per fare fast input).
private static class InputReader implements java.io.Closeable {
private final java.io.InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(java.io.InputStream stream) {
this.stream = stream;
}
@Override
public void close() {
try {
this.stream.close();
} catch (java.io.IOException e) {
}
}
public int read() {
if (numChars == -1) {
throw new java.util.InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (java.io.IOException e) {
throw new java.util.InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = eatWhite();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new java.util.InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = eatWhite();
long sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9') {
throw new java.util.InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = eatWhite();
StringBuilder res = new StringBuilder();
do {
if (Character.isValidCodePoint(c)) res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String readLine() {
StringBuilder res = new StringBuilder();
while (true) {
int c = read();
if (c == '\n' || c == '\r' || c == -1) break;
if (Character.isValidCodePoint(c)) res.appendCodePoint(c);
}
return res.toString();
}
private int eatWhite() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
return c;
}
public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}
Non ricordarsi che, anche nei giorni precedenti potevi leggere un libro, anche se non è quello con più pagine per quella scadenza è chiaramente sbagliato.
Come sospettavo, quello non è l’unico problema, la mia complessiva visione del problema era sbagliata.
Grazie soprattutto all’aiuto in dm di @Fxby, cambiando sia le strutture dati che il modo di intendere il problema l’ho risolto.