# Chiarimenti per il codice di Collezionismo

**URL:** <https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201>\
**Category:** Chiarimenti\
**Created:** [17 Aprile 2023, 7:42pm UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201 "2023-04-17T19:42:12Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![jvsx](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/b782af/32.png) [@jvsx](https://forum.olinfo.it/u/jvsx)\
**Post date:** [17 Aprile 2023, 7:42pm UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201/1 "2023-04-17T19:42:12Z")

</div>

```auto
#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.

---

<div class="post-metadata">

**Author:** ![aleeeee1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/aleeeee1/32/1374_2.png) [@aleeeee1](https://forum.olinfo.it/u/aleeeee1)\
**Post date:** [17 Aprile 2023, 8:16pm UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201/2 "2023-04-17T20:16:50Z")

</div>

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

```python
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}")

```

---

<div class="post-metadata">

**Author:** ![fabriziogiacomi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fabriziogiacomi/32/2523_2.png) [@fabriziogiacomi](https://forum.olinfo.it/u/fabriziogiacomi)\
**Post date:** [18 Aprile 2023, 7:30am UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201/3 "2023-04-18T07:30:15Z")

</div>

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:

> **[2 - Collezionismo di robot](https://wiki.olinfo.it/it/2021/territoriali/collezionismo)**
>
> Problema collezionismo delle Selezioni Territoriali OII 2021.

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.

---

<div class="post-metadata">

**Author:** ![l.frasson](https://forum.olinfo.it/user_avatar/forum.olinfo.it/l.frasson/32/2823_2.png) [@l.frasson](https://forum.olinfo.it/u/l.frasson)\
**Post date:** [5 Novembre 2023, 1:49pm UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201/4 "2023-11-05T13:49:30Z")

</div>

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

```auto
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!

```

---

<div class="post-metadata">

**Author:** ![Mazza7](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mazza7/32/2689_2.png) [@Mazza7](https://forum.olinfo.it/u/Mazza7)\
**Post date:** [5 Novembre 2023, 2:53pm UTC](https://forum.olinfo.it/t/chiarimenti-per-il-codice-di-collezionismo/8201/5 "2023-11-05T14:53:59Z")

</div>

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