Const n=15; var i,np,nn,amax:integer; a:array[1..n] of integer; begin Randomize; Write('Исходный массив: '); np:=0; nn:=0; for i:=1 to n do begin a[i]:=Random(51)-15; Write(a[i],' '); if a[i]>0 then Inc(np) else if a[i]<0 then Inc(nn); end; Writeln; if np/nn>2 then begin amax:=a[i]; for i:=2 to n do if a[i]>amax then amax:=a[i]; Write('Выходной массив: '); for i:=1 to n do begin if a[i]<0 then a[i]:=1 else if a[i]>0 then a[i]:=a[i]*amax; Write(a[i],' ') end; Writeln end else Writeln('В массив изменения не вносятся') end.
Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности вершин, то общее число рёбер будет суммой по всем компонентам связности:
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.
Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.
Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов:
Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
n=15;
var
i,np,nn,amax:integer;
a:array[1..n] of integer;
begin
Randomize;
Write('Исходный массив: ');
np:=0; nn:=0;
for i:=1 to n do begin
a[i]:=Random(51)-15;
Write(a[i],' ');
if a[i]>0 then Inc(np)
else if a[i]<0 then Inc(nn);
end;
Writeln;
if np/nn>2 then begin
amax:=a[i];
for i:=2 to n do
if a[i]>amax then amax:=a[i];
Write('Выходной массив: ');
for i:=1 to n do begin
if a[i]<0 then a[i]:=1
else
if a[i]>0 then a[i]:=a[i]*amax;
Write(a[i],' ')
end;
Writeln
end
else Writeln('В массив изменения не вносятся')
end.
Пример работы программы
Исходный массив: 28 8 21 32 0 26 30 11 35 21 14 6 0 -4 -8
Выходной массив: 980 280 735 1120 0 910 1050 385 1225 735 490 210 0 1 1