Se dau n cifre. Cu acestea trebuie să formăm k numere astfel încât suma acestor k numere să fie minimă. Singura condiţie pe care trebuie să o respectăm în formarea celor k numere este ca cifrele nule să nu se afle la începutul unui număr.
Cerința
Determinaţi suma minimă care se poate obţine prin construirea a k numere care să utilizeze toate cele n cifre.
multumesc mult ca ati citit si as aprecia daca m-ar putea ajuta cineva
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
int main()
{
int n,k,a,b,c;
cin >> n;
int vf[10]={0};
for (a=1; a<=n; a++) {
cin >> c; ++vf[c];
}
cin >> k;
++k;
int vk[k]; for (a=1; a<k; a++) vk[a]=0;
for (c=0; c<10; c++) cout << vf[c] << " ";
cout << endl;
a=1; b=1;
while (a<k) {
if (vf[b]) {
vk[a]=b; --vf[b];
++a; --n;
}
else {
++b; if (b>9) b=1;
}
}
for (a=1; a<k; a++) {
cout << vk[a] << " ";
}
cout << endl;
int pk[k]; for (a=1; a<k; a++) pk[a]=10;
while (n) {
a=1; b=0;
while (a<k && n) {
if (vf[b]) {
vk[a]=vk[a]*pk[a]+b; --vf[b];
pk[a]=pk[a]*10; ++a; --n;
}
else {
++b; if (b>9) b=0;
}
}
}
for (a=1; a<k; a++) {
cout << vk[a] << " ";
}
int s=0;
for (a=1; a<k; a++) {
s=s+vk[a];
}
cout << endl << s;
return 0;
}
Explicație:
- Completare vf vectorul frecvenței cifrelor și afișare vf;
- Completare vk vectorul a k numere cu prima cifră și afișare vk;
- Completare vk cu cifrele rămase din vectorul vf și afișare vk;
- Calculare sumă a numerelor din vk cu afișare.
p.s. au fost 3 afișeri intermediare (pe care poți să le ștergi) pentru a verifica că codul (logica) e corect...
Sper că nu am greșit și te-am ajutat... Succese la cercetare...
Da, am considerat că k<n, de altfel problema nu are rezolvare...