# Collezionismo(6/15)

**URL:** <https://forum.olinfo.it/t/collezionismo-6-15/8391>\
**Category:** Aiuto\
**Created:** [1 Luglio 2023, 4:27pm UTC](https://forum.olinfo.it/t/collezionismo-6-15/8391 "2023-07-01T16:27:48Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![MLR1](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ebca7d/32.png) [@MLR1](https://forum.olinfo.it/u/MLR1)\
**Post date:** [1 Luglio 2023, 4:27pm UTC](https://forum.olinfo.it/t/collezionismo-6-15/8391/1 "2023-07-01T16:27:49Z")

</div>

Buongiorno, è da un giorno che provo a risolvere questo problema ma non riesco a capire il motivo per cui non fa 15/15

#include \<bits/stdc++.h\>

using namespace std;

void printv(vector\<vector\>S,int K){  
for(int i = 0;i\<K;i++){  
if(i)cout\<\<‘\n’\<\<endl;  
for(int i1 = 0;i1\<S[i].size();i1++){  
cout\<\<S[i][i1]\<\<endl;  
}  
}  
}

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

```
vector<int> C(N);
for (int i = 0; i < N; i++) {
    cin >> C[i];
}

// aggiungi codice...
int64_t risposta = 0;
sort(C.begin(),C.end());

if(K == 1)risposta = C[N-1]-C[0];

else if(K == N)risposta = 0;

else{
    vector<vector<int>>S(K);
    for(int i = 0;i<K;i++)for(int i1 = 0;i1<N/K;i1++)S[i].push_back(C[i*(N/K)+i1]);
    for(int i = N%K;i>0;i--)S[K-1].push_back(C[N-i]);
    
    //if(t == 1)printv(S,K);
    
    for(int i = 0;i<K-1;i++){
    	int dmin = S[i].back()-S[i].front()+ S[i+1].back()-S[i+1].front();
    	while(1){
    		if(S[i+1].size() == 1)break;
			S[i].push_back(S[i+1].front());
    		S[i+1].erase(S[i+1].begin());
    		int at = S[i].back()-S[i].front()+ S[i+1].back()-S[i+1].front();
			if(at<=dmin)dmin = at;
			else{
				S[i+1].insert(S[i+1].begin(),S[i].back());
				S[i].pop_back();
				break;
			}
    	}
    	while(1){
    		if(S[i].size() == 1)break;
    		S[i+1].insert(S[i+1].begin(),S[i].back());
			S[i].pop_back();
    		int at = S[i].back()-S[i].front()+ S[i+1].back()-S[i+1].front();
			if(at<=dmin)dmin = at;
			else{
				S[i].push_back(S[i+1].front());
    			S[i+1].erase(S[i+1].begin());
				break;
			}
			
		}
	}
	for(int i = 0;i<K;i++){
		risposta+= S[i].back()-S[i].front();
	}
}

cout << "Case #" << t << ": " << risposta << "\n";

```

}

int main(){  
// se preferisci leggere e scrivere da file  
// ti basta decommentare le seguenti due righe:

```
freopen("collezionismo_input_11.txt", "r", stdin);
freopen("output.txt", "w", stdout);

int T;
cin >> T;

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

return 0;

```

}

---

<div class="post-metadata">

**Author:** ![alecurse](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alecurse/32/2642_2.png) [@alecurse](https://forum.olinfo.it/u/alecurse)\
**Post date:** [1 Luglio 2023, 5:01pm UTC](https://forum.olinfo.it/t/collezionismo-6-15/8391/2 "2023-07-01T17:01:35Z")

</div>

La soluzione è più semplice di così. Ti propongo dei suggerimenti presi dalla [wiki](https://wiki.olinfo.it):

**Hint 1.** Ordina i modellini per valori crescenti di C\_i.

**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 K - 1 “separatori” tra intervalli consecutivi.

**Hint 4.** A questo punto, la somma dei fattori di discrepanza dipende solo dalle differenze dei C\_i dei modellini adiacenti a ciascun separatore.