Chiarimenti per il codice di Collezionismo

Chiarimenti
1 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void solve(int t) {
    int N, K;
    cin >> N >> K;

    vector<int> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    sort(C.begin(), C.end());

    vector<int> differences(N - 1);
    for (int i = 0; i < N - 1; i++)
        differences[i] = C[i] - C[i + 1];
    sort(differences.begin(), differences.end());

    int ans = C[N - 1] - C[0];
    for (int i = 0; i < K - 1; i++)
        ans += differences[i];

    cout << "Case #" << t << ": " << ans << "\n";
}

int main() {
    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) solve(t);

    return 0;
}

Ho trovato questo codice sulla wiki delle olimpiadi come risoluzione di “Collezionismo”, qualcuno potrebbe gentilmente spiegarmi perché mette le righe :
int ans = C[N - 1] - C[0];
for (int i = 0; i < K - 1; i++)
ans += differences[i];
cioè vorrei sapere il ragionamento dietro. Grazie mille.

2

Sinceramente non ho capito neanche io il codice proposto, ma ho capito “l’idea” e ho implementato il mio. Magari può esserti d’aiuto:

def solve(t):
    input()
    N, K = map(int, input().strip().split())
    C = list(map(int, input().strip().split()))

    C.sort()

    distanze = [abs(C[i+1] - C[i]) for i in range(len(C)-1)]
    distanze.sort()

    risposta = sum(distanze[:len(distanze) - K + 1])

    print(f"Case #{t}: {risposta}")
3

Ciao, il codice che si trova sulla wiki è anche argomentato con il ragionamento dietro al codice. Se ti interessa sapere matematicamente perché ti consiglio di andare a leggertelo da qui:

Semplificando il ragionamento, il “fattore di discrepanza” di ogni scaffale si può ottenere dalla somma dei fattori di discrepanza di intervalli più piccoli, salvati nel vettore differences sommata alla discrepanza tra il primo e l’ultimo elemento.

4

Ciao,
ho provato ad applicare la soluzione proposta ai casi di esempio:

6 3
4 42 23 0 21 2

6 robot, 3 scaffali
ordino i robot
0 2 4 21 23 42

calcolo le differenze
2 (0,2) 2 (2,4)  17(4,21) 2 (21,23) 19 (23,42)

le ordino
2 2 2 17 19

ans = Cultimo-c0 + (k-1) differenze
ans = (42-0) + 2+2= 46 e non 6 come nel secondo case di esempio.

Cosa sto sbagliando? Ho interpretato male il problema o la soluzione?
Grazie!
5

In realtĂ  le differenze sono calcolate con il numero meno il successivo, quindi essendo ordinati sono negative.
Ottieni: -2, -2, -17, -2, -19
Ordinato: -19, -17, -2, -2, -2
Poi calcoli: 42 - 0 - 19 - 17 = 6

1 Mi Piace