Collezionismo(6/15)

Aiuto
1

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;

}

2

La soluzione è più semplice di così. Ti propongo dei suggerimenti presi dalla wiki:

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.