Aiuto per Precise Average 2 (ois_avg2)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Precise Average 2.

Sono uno che ha appena iniziato a scrivere il codice in c++. Ho provato a risolvere questo problema prima in python e mi ha dato tutti subtask giusti, solo che alcuni superano il limite di tempo. Ho deciso quindi di tradurlo in c++. Però ora il tempo non supera più ma dà alcuni task sbagliati anche se ho scritto uguale a quello di python e non riesco a trovare l’errore.

Ecco il mio codice:

// NOTE: it is recommended to use this even if you don't understand the following code.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");

    int N;
    long long K;
    cin >> N >> K;
    
    vector<long long> P(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i];
    
    long long C = 0;
    
    
    // INSERT YOUR CODE HERE

    long long right = 100000000; 
    long long left = 0;

    long long initial_sum = accumulate(P.begin(), P.end(), 0LL);
    long long target_sum = N * K;
    long long need = abs(initial_sum - target_sum);

    while (left <= right) {
        long long mid = (left+right) / 2;
        long long max_variation = 0;

        if (initial_sum < target_sum) {
            max_variation = N * mid;
        } else {
            for (int i=0; i<N; i++) {
                max_variation = max_variation + min(mid, P[i]-1);
            }
        }

        if (max_variation >= need) {
            C = mid;
            right = mid -1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << C << endl;
    return 0;
}

Qua riporto il mio codice in python:

#!/usr/bin/env python3
# NOTE: it is recommended to use this even if you don't understand the following code.

import sys
import math

# uncomment the two following lines if you want to read/write from files
# sys.stdin = open('input.txt')
# sys.stdout = open('output.txt', 'w')

N, K = map(int, input().strip().split())

P = list(map(int, input().strip().split()))

C = 0

right = 100000000
left = 0

initial_sum = sum(P)
target_sum = N * K
need = abs(initial_sum - target_sum)

while left <= right:
    mid = (left + right) // 2
    max_variation = 0

    if initial_sum < target_sum:
        max_variation = N * mid
    else:
        for i in range(N):
            max_variation += min(mid, P[i] - 1)

    if max_variation >= need:
        C = mid
        right = mid - 1  
    else:
        left = mid + 1   

print(C)

sys.stdout.close()

Grazie mille in anticipo!

2

Ho trovato l’errore che fallisce per c++, ma non capisco il motivo qualcuno può spiegarmelo? Il caso che fallisce sta nel modo in cui gestico la situazione: initial_sum < target_sum.

Prima lo gestivo dentro la ricerca binaria, ma esiste una formula che lo calcola direttamente. Il mio dubbio però è perché non funziona in c++ ma in python dava giusto se lo gestivo dentro?

if (initial_sum < target_sum) {
        long long C = (need + N - 1) / N;
        cout << C << "\n";
        return 0;
    }

Grazie mille in anticipo!

3

A dire il vero mi sembra che le soluzioni in python e c++ sbaglino gli stessi testcase (a parte quando la soluzione in python fa TLE, quindi non vedi che l’output è errato perché l’esecuzione viene terminata prima).

1 Mi Piace