Non so quale sia il problema, ma sbaglio solamente una task (80/100), si accettano suggerimenti.
Grazie in anticipo.
#include <bits/stdc++.h>
using namespace std;
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N, K;
cin >> N >> K;
vector<int>distances(N);
for(int i = 0; i != N; i++) {
cin >> distances[i];
}
int res = 0;
for(int i = 0; i != N - K; i++){
for(int j = i + 1; j != i + K + 1; j++) {
int tmp = abs(distances[i] - distances[j]);
if(tmp > res)
res = tmp;
}
}
cout << res << endl;
}
ciao! il tuo codice va in tle perchè la soluzione ha una complessità troppo elevata, la tecnica che serve in questo caso è la sliding window (che è molto comune).
prima di leggere lo spoiler, ti lascio un paio di hint per arrivarci da solo:
1- se per ogni sottoarray di dimensione K potessi trovare facilmente la “tristezza massima” (con facilmente intendo in O(1)) quale sarebbe la soluzione per l’intero array?
2- ora, per trovare questa tristezza massima nella finestra in O(1) e poterla anche fare scivolare velocemente dovresti potere avere una struttura dati che tiene al suo interno alcuni valori ordinati in base alla chiave, qual’è?
3- bene ora che abbiamo tutto questo manca solo come farla scivolare?
Soluzione:
Sostanzialemente pensa: avendo una finestra grande K e facendola scorrere rimuovendo l’elemento più a sinistra e aggiungendone uno a destra in O(1) con una mappa, decrementando (o rimuovendo se la sua frequenza è = 1) la frequenza dell’elemento più a sinistra e incrementando di uno la frequenza di quello più a destra che aggiungiamo , grazie a questa stessa mappa all’interno della determinata finestra puoi trovare anche la “tristezza massima” in quell’intervallo in O(1) prendendo il primo e l’ultimo elemento della mappa, perciò facendo scorrere lungo tutto l’array e trovando la “tristezza massima” in ogni intervallo la soluzione per tutto l’array sarà la massima tra le tristezze che trovi scorrendo.
Sorry per le tante ripetizioni ma spero di risultare il piĂą chiara possibile
Propongo una struttura dati alternativa più veloce (anche se un po’ più complicata da implementare) per gestire la sliding window.
Teniamo una deque<pair<int, int>>, quando ci spostiamo a destra nella posizione i facciamo le seguenti operazioni:
P.S. Penso che il modo più agevole di risolvere il problema con le queue sia tenersi sia una maxqueue sia una minqueue, l’implementazione della seconda è comunque parallela a quella della prima.
Io invece ho provato a risolverlo con un set per gestire la window e un’altro per salvare le varie tristezze massime però ottengo 90/100 perchè sbaglia 2 test case e continuo a non capire perchè.
#include <stdio.h>
#include <assert.h>
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
int sadness(int N, int K, int V[]) {
multiset<int> win; //window
set<int, greater<int>> depre; //salvo le tristezze
for(int i=0; i<(K+1); i++) //prima window
{
win.insert(V[i]);
}
for(int i=0; i<(N-K+1); i++)
{
int tmax= abs(*win.begin()-*(prev(win.end())));
depre.insert(tmax);
win.erase(win.find(V[i])); //cancella sempre il numero minimo e non l'ultimo inserito
//però mi da un punteggio migliore rispetto a win.erase(win.find(V[i]))
//che teoricamente cancella solo il primo numero della window ed è più corretto
win.insert(V[K+i]);
}
int risposta=*(depre.begin());
return risposta;
}
int V[MAXN];
int main() {
FILE *fr, *fw;
int N, K, i;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%d", &V[i]));
fprintf(fw, "%d\n", sadness(N, K, V));
fclose(fr);
fclose(fw);
return 0;
}