Non ho idea di dove sia l'errore in un problema banale (Precise Average)

Aiuto
1

Questo il codice, e la logica è poca e a mio parere semplice

#include <bits/stdc++.h>
using namespace std;
int main() {
   int N, K;
   cin >> N >> K;
   
   int somma = 0, media = 0;
   vector<int> P(N);
   for (int i = 0; i < N; ++i)
   {
   	cin >> P[i];
   	somma += P[i];
   }
   media = somma/N;
   
   int ans = 0;
   int contatore = N-1;
   
   sort(P.begin(), P.end());
   
   if (media == K)
   {
   	ans = 0;
   }
   
   else if (media < K)
   {
       ans = 1;
   }
   
   else 
   {
   	cerr << "entrato in media>K" << endl;
   	while (media > K)
   	{
   		media -= (P[contatore]-1)/N;
   		contatore--;
   		ans++;
   	}
   }
   
   
   cout << ans << endl;

   return 0;
}

Ammeno che l’errore non sia nel come io mi comporto se la media è maggiore di quella da raggiungere, che è si il caso più difficile ma dovrebbe comunque essere banale (P[contatore]-1 perché il prezzo min è di 1 bytedollaro).
Grazie a tutti in anticipo.

2

Hai fatto un po’ di caos con i tipi numerici.
Intanto stai sempre attento a non overfloware gli interi (int tiene fino a 2^{31}\approx2\cdot10^9, ma la variabile somma potrebbe contenere valori fino a 2\cdot10^{11}).

Inoltre ricorda che in C++ dividere due interi ti restituisce un intero (in particolare il risultato viene approssimato per difetto), quindi stai introducendo dell’errore ogni volta che una divisione non ha un risultato intero.

Detto questo, ti conviene cercare un modo di risolvere il problema senza divisioni con risultati non interi: i tipi non interi (float, double, etc.) hanno una precisione limitata e quindi un’incertezza che si propaga in modo non banale da prevedere quando vi si opera.

2 Mi Piace
3

io ho fatto in questo modo e mi da 100/100

Riepilogo 
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

int solve(long long n, long long k, long long s, vector<int> &p) {

    if(s == (n*k)) return 0;
    if(s < (n*k)) return 1;

    sort(p.begin(), p.end(), greater<int>());

    int c=0;

    while(s>(n*k)) {
        s -= (p[c]-1);
        c++;
    }


    return c;
}

int main() {

    long long n,k,s=0;

    in >> n >> k;

    vector<int> p(n);

    for(int &x: p) {in >> x; s+=x;}


    out << solve(n,k,s,p);


    return 0;
}
1 Mi Piace