7. Башня Петя в очередной купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
Входные данные
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 1000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 103).
Выходные данные
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.
Гарантируется, что в оптимальном разбиении неприступность крепости не превосходит 2 × 109.
Примеры
входные данные
1 1
1
выходные данные
1
1
входные данные
2 1
1 1000
выходные данные
2
1 2
входные данные
8 3
1 2 3 4 1 6 7 8
выходные данные
2
2 6
Код нужен на C++
Відповідь:
#include <iostream>
#include<string>//для std::string,length()
#include<iomanip>//для std::setw()
struct kid{
std::string name;
bool gender;
float height;
};
int main(int argc, char** argv) {
struct kid kids[]={
"Tom",1,1.34,
"Sara",0,1.54,
"John",1,1.65,
"Kate",0,1.86,
"Emily",0,1.53,
"Lily",0,1.57,
"Oscar",1,1.76,
"James",1,1.73,
"William",1,1.71,
"George",1,1.67,
"Noah",1,1.61,
"Leo",1,1.75,
"David",1,1.71,
"Albert",1,1.68,
"Austin",1,1.84,
"Mia",0,1.65,
"Ruby",0,1.64,
"Scarlett",0,1.54,
"Isabelle",0,1.45,
"Ellie",0,1.65
};
double medium=0.0;
int n=sizeof(kids)/sizeof(kids[0]);
int t=0;
for(int i=0;i<n;i++){
std::cout<<kids[i].name<<std::setw(12-kids[i].name.length())<<kids[i].gender<<std::setw(7)<<kids[i].height<<std::endl;
if(kids[i].gender==true){
medium+=kids[i].height;t++;}
}
medium/=t;
std::cout<<"\nMedium height of boys= "<<medium<<std::endl<<std::endl;
for(int i=0;i<n;i++){
if(kids[i].gender==1){
if(kids[i].height<medium){
std::cout<<kids[i].name<<std::setw(12-kids[i].name.length())<<kids[i].gender<<std::setw(7)<<kids[i].height<<std::endl;
}
}
}
system("pause");
return 0;
}
Массив - это множество однотипных элементов, объединённых общим именем и занимающих в компьютере определённую область памяти. Количество элементов в массиве всегда конечно. В общем случае массив - это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.
Другими словами можно сказать, что массив представляет собой фиксированное количество упорядоченных однотипных компонент, снабженных индексами, т.е. является совокупностью конечного числа данных одного типа. В качестве элементов массива можно использовать любой тип данных, поэтому вполне правомерно существование массивов записей, массивов указателей, массивов строк, массивов и т.д.
Массивы могут быть:
одномерными (одна строка – несколько столбцов);
многомерными (несколько строк – несколько столбцов).
Для создания массива его предварительно необходимо описать либо в разделе var, либо в разделе type. Для задания массива используется зарезервированное слово array, после которого указывается тип индекса (-ов) компонент (в квадратных скобках) и после слова of - тип самих компонент!