Имеем доску, в которую на определенном расстоянии друг от друга вбиты гвозди. Любые два гвоздя можно соединить веревкой. Надо соединить веревкой некоторые пары гвоздей так, чтобы к каждому гвоздю была привязана веревка, а расстояние между гвоздями было минимальным.
Вводные данные: дано целое число N — количество гвоздей (2 ≤ N ≤ 100). На другой строчке даны N чисел — координаты гвоздей (разные, неотрицательные числа, которые не превышают 10000).
Вывод: Вывести минимально возможную длину всех веревок.
Примеры Ввода/Вывода:
+------------------+-------------------+ | стандартный ввод | стандартный вывод | +------------------+-------------------+ | 6 | 5 | | 3 4 12 6 14 13 | | +------------------+-------------------+ | 7 | 5 | | 3 2 1 4 5 7 9 | | +------------------+-------------------+
Мой код:
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
int n, sk[10000], min[10000], not[10000], tot;
int ats=0;
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
cin >> sk[i];
}
for(int a=0;a<n;a++)
{
min[a]=11000;
}
for(int s=0;s<n;s++)
{
not[s]=0;
}
for(int y=0;y<n-1;y++)
{
if(not[y]==1){}
else{
for(int e=0;e<n;e++)
{
if(y==e){}
else
{
if((abs(sk[y]-sk[e]))<min[y])
{
min[y]=abs(sk[y]-sk[e]);
tot=e;
}
else if((abs(sk[y]-sk[e]))==min[y])
{
if(not[tot]==1)
{
}
else
{
min[y]=abs(sk[y]-sk[e]);
tot=e;
}
}
}
}
for(int l=0;l<n;l++)
{
if(y==l){ }
else if((abs(sk[y]-sk[l]))==min[y] && tot==l)
{
not[l]=1;
}
}
//cout<<"dlia cifri: "<<sk[y]<<" mimimum "<<min[y]<<endl;
}
}
for(int z=0;z<n;z++)
{
if(min[z]!=11000)
{
ats+=min[z];
}
}
cout << ats << endl;
return 0;
}
3 4 12 6 14 13
получилось решение5
??? Какие пары гвоздей предлагается связывать, чтобы общая длина получилась5
?