Puoi leggere e provare a risolvere il problema collezionismo
visitando la piattaforma Terry.
Hint 1. Ordina i modellini per valori crescenti di .
Hint 2. Assumento che i modellini siano ordinati, dimostra che c'è una ripartizione ottima in cui ogni scaffale contiene un intervallo di modellini.
Hint 3. Puoi vedere una tale ripartizione come una scelta di "separatori" tra intervalli consecutivi.
Hint 4. A questo punto, la somma dei fattori di discrepanza dipende solo dalle differenze dei dei modellini adiacenti a ciascun separatore.
Iniziamo ordinando i modellini in ordine crescente di . D'ora in poi, assumeremo quindi che . La prima osservazione cruciale è che esiste una soluzione ottima (cioè una ripartizione dei modellini in scaffali che minimizza la somma dei fattori di discrepanza) in cui il -esimo scaffale forma un intervallo del tipo . Questo fatto è abbastanza intuitivo, ma la dimostrazione è un po' laboriosa, e per questo è riportata sotto spoiler.
Supponiamo di avere una ripartizione in cui non tutti gli scaffali formano intervalli. Sia il più piccolo indice tale che il modellino non appartiene a un intervallo. Dimostreremo che esiste una ripartizione la cui somma dei fattori di discrepanza è minore o uguale di quella precedente, in cui tutti i modellini di indice appartengono a un intervallo.
Sia l'indice dello scaffale a cui appartiene il modellino . Chiamiamo il numero di modellini che appartengono allo scaffale , e consideriamo la ripartizione in cui, detto lo scaffale a cui appartiene il modellino :
Detto in modo meno formale: stiamo "comprimendo" lo scaffale a cui appartiene in modo che formi un intervallo, e spostando opportunamente gli altri modellini in modo che l'ordine degli scaffali diversi da non cambi.
È facile notare che in questa nuova ripartizione ogni scaffale ha un fattore di discrepanza che non supera quello della precedente. Inoltre, adesso il modellino appartiene a un intervallo, così come tutti quelli precedenti (che non sono stati modificati).
Per discesa infinita, dopo un certo numero di operazioni di questo tipo avremo ottenuto una ripartizione in cui ogni scaffale forma un intervallo, senza aver mai aumentato la somma dei fattori di discrepanza.
La prossima idea consiste nel cambiare punto di vista. Notiamo infatti che a ogni ripartizione dei modellini in intervalli corrisponde univocamente una scelta di "separatori", per cui un intervallo è identificato da due separatori consecutivi (o, nel caso del primo e dell'ultimo intervallo, da un solo separatore, rispettivamente il primo e l'ultimo).
Se l'-esimo separatore () separa la coppia , otteniamo che la somma dei fattori di discrepanza è data da
Ovvero, la somma dei fattori di discrepanza è data da una costante () più la somma delle differenze dei valori di collezionismo dei modellini adiacenti a ciascun separatore.
Basterà quindi ordinare tali differenze (che sono ) in ordine crescente e selezionare le prime .
La complessità della soluzione è dominata dai due ordinamenti, ciascuno dei quali richiede tempo .
C++
#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;
}