Buonasera, potreste gentilmente aiutarmi a capire quale caso non ho considerato? Cosa potrei fare per migliorare il codice? Non penso si tratti di overflow perchè nell’ultimo testcase del subtask 4 mi risponde in maniera corretta.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
int sfangate(int N, int V[]) {
vector <int> salva(MAXN);
int somma=0;
int ans=0;
for(int i=0; i<N; i++){
salva[i]=V[i];
}
sort(salva.begin(), salva.end());
for(int i=0; i<N; i++){
salva[i]*=-1;
for(int j=0; j<N; j++) somma+=salva[j];
if(somma>=0){
ans++;
break;
}
else{
somma=0;
ans++;
}
}
return ans;
}
int V[MAXN];
int main() {
FILE *fr, *fw;
int N, i;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%d", &N));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%d", &V[i]));
fprintf(fw, "%d\n", sfangate(N, V));
fclose(fr);
fclose(fw);
return 0;
}
Ciao, a me sembra che il tuo codice fallisca nei casi di test con constraints più grandi. In più, l’ultimo testcase del 4 va in TLE. L’approccio è strano: ne esiste uno migliore e più preciso. Come puoi decidere quali entrate “sfangare” e quali no?
Suggerimenti:
-
Puoi usare std::sort() su V[], per fare il sorting dal primo elemento all’N-esimo elemento usa std::sort(V, V + N).
-
Ha senso ricalcolare ogni volta l’array delle somme?
-
Calcola una volta le somme, dopodiché per sfangare l’i-esima entrata basta aggiungere alle somme -2 \times V[i]
Se ti serve una mano chiedi pure!
Buona giornata 
Ciao Fabrizio, ti spiego brevemente cosa fa il codice. Riordina l’array dal più piccolo al più grande quindi avremo così i numeri negativi che sono più piccoli all’inizio dell’array. All’inizio faccio diventare l’i-esimo elemento positivo essendo il più piccolo numero e controllo se basta “girare” questo numero per vedere se la somma è positiva quindi >=0 se lo è allora il risultato è ans. Altrimenti azzero la variabile somma così da non avere problemi con le verifiche successive e incremento lo stesso la variabile ans dato che comunque abbiamo “girato” un numero. Potresti spiegarmi perché moltiplichi per -2 e non -1? È normale che moltiplicando per un numero più grande ci sono meno sfangate da fare, da output corretto??
Grazie per il chiarimento! La tua logica è corretta, tuttavia non è efficiente. Il problema per cui prendi 30/100 è che salvi i valori di V dentro salva (ordinando direttamente V con std:sort() il programma funziona). Il vero problema è l’ultimo test del subtask 4, in cui va comunque in TLE:
Ti spiego brevemente perché -2 e non -1: ipotizzamo di avere solo un’entrata di valore -5. Somma varrà ovviamente -5. “Sfangando” l’entrata, il suo valore arriverà a 5. In questo caso, però, aggiungendo alla somma -5 \times -1 si otterrà 0, mentre la somma reale è 5.
Come risolvere il problema:
-
Usa std::sort() direttamente su V.
-
Calcola una sola volta la somma.
Spero che il messaggio sia stato chiaro!
1 Mi Piace
Ciao Fabrizio, grazie infinite per l’aiuto. Ho semplicemente fatto sort(V, V+N) e sostituito salva con il vettore V, togliendo totalmente il vettore salva però non ho fatto *-2 ed è andato lo stesso. L’ultimo caso bastava mettere #pragma GCC optimize("Ofast") prima di includere la libreria come avevo già fatto prima d’altronde. I trucchi del mestiere 
ahahhahaha
1 Mi Piace
