Я думаю, что вектор гораздо лучше, чем массивы: простой и динамический.
В.И.
Вверх, все выше, я держу…
Динамические структуры:
В е к т о р
Методы работы с вектором:
1) vector<int> v(10); - Объявление вектора в 10 элементов типа int
2) push_back() –добавление нового элемента в конец вектора
3) size() – количество элементов в векторе
4) pop_back() — удалить последний элемент
5) clear() — удалить все элементы вектора (очистка)
6) empty() — проверить вектор на пустоту
7) sort(v.begin(), v.end()) - сортировка вектора по возрастанию
8) sort(v.rbegin(), v.rend()) - сортировка вектора по убыванию
9) emplace() - вставка элемента в начало вектора
10) emplace_back() - вставка элемента в конец вектора
11) v.erase(v.begin()) - стираем 0-й элемент вектора (первый в ряду)
12) v.erase(v.begin()+2,v.begin()+6) - стираем с 3-го по 6-й элементы вектора,
13) v.insert(v.begin(), 1); // добавили 1 в начало
14) v.insert(v.end(), 4); // добавили 4 в конец
[] - доступ к элементам вектора (как и для обычных массивов: v[9] или v[0])
include <vector>
или
include <bits/stdc++.h>
Пример №1: Объявить вектор 10 элементов, заполнить его степенями двойки от 1-й до 10-й. Вывести вектор:
1) простым повторением 10 раз (т.к. размерность заранее известная)
2) до конца, используя метод size()
Способ №1
Способ №2
Пример №2:
Объявить вектор без размера, добавить в вектор 10 элементов, заполняя его нечетными числами. Вывести заполненный вектор в строку.
Пример №3: Объявить вектор без размера, добавить в вектор n элементов и заполнить его числами от 1 до n. Вывести вектор. Поставить четвертый (номер 3) элемент вектора предпоследним. Например:
12
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 5 6 7 8 9 10 11 4 12
Пример №4: Объявить вектор без размера, добавить в вектор n элементов и заполнить его нечетными числами. Произвести циклический сдвиг влево на один элемент. Например:
9
1 3 5 7 9 11 13 15 17
3 5 7 9 11 13 15 17 1
Пример №5. Вставка элемента вектора по запросу номера (в какой элемент по номеру) и значения (какое значение вставить).
Пример для 5-ти элементов в векторе (после вставки будет 6).
vector <int> v;
int i,n,k,n_ins,n_v;
cin >> n;
for (i=0; i<n; i++) {
cin >> k;
v.push_back(k); }
for (i=0; i<v.size(); i++) cout << v[i] << " ";
cout << endl;
cin >> n_ins >> n_v;
v.insert(v.begin()+n_ins,n_v);
for (i=0; i<v.size(); i++) cout << v[i] << " ";
Пример №6: Объявить вектор 14 элементов, заполнить его случайно двузначными числами. Вывести вектор. Отсортировать вектор по возрастанию. Вывести вектор (еще раз) в отсортированном виде.
Для справки:
Заполнение целочисленного массива случайным образом из отрезка [15, 35]
for ( i = 0; i < N; i ++ ) a[i] = rand() % 20 + 15;
Заполнение вещественного массива случайным образом из отрезка [15, 35]
for ( i = 0; i < N; i ++ ) b[i] = (float)rand() % 20 + 15;
Пример №7: Объявить вектор 14 элементов, заполнить его случайными двузначными числами. Вывести вектор. Отсортировать вектор по убыванию. Вывести еще раз отсортированный вектор.
Пример №8: Объявить вектор без размера, добавить в вектор n элементов и заполнить его натуральными числами от 1 до n. Вывести вектор. Выполнить циклический сдвиг вектора на k элементов вправо. Например, для n=12 и k=2:
12 2
1 2 3 4 5 6 7 8 9 10 11 12
11 12 1 2 3 4 5 6 7 8 9 10
vector <int> v;
int n,i,s,k;
cin >> n >> k;
for (i=0; i<n; i++) v.push_back(i+1);
for (i=0; i<v.size(); i++) cout << v[i] << " ";
cout << endl;
for (i=0; i<k; i++){
s=v[v.size()-1]; // запоминание последнего
v.pop_back(); // удаление
v.insert(v.begin(),s); // вставка
}
for (i = 0; i < v.size(); i++) cout << v[i] << " ";
Пример №9 «Демократия в опасности»: В одном из островных государств Карибского бассейна все решения принимались простым большинством голосов на общем собрании граждан. Одна из партий, стремясь прийти к власти законным путем, смогла добиться реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей. Суть реформы состояла в следующем: все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу проводилось отдельно в каждой группе. Группа высказывается «за», если «за» голосует более половины людей в этой группе, а иначе считалось, что группа высказывается «против». После голосования в группах подсчитывалось количество групп, высказавшихся «за» и «против», и вопрос решался положительно в том, когда групп, высказавшихся «за», оказывалось более половины общего количества групп. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов!
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5, 7 человек соответственно. Тогда партии достаточно иметь трех сторонников в каждой из первых двух групп, и она сможет провести решение всего шестью голосами «за», вместо девяти, необходимых при общем голосовании.
Вам надо написать программу, которая определяет по заданному разбиению избирателей на группы минимальное количество сторонников партии, достаточное, при некотором распределении их по группам, для принятия любого решения.
Входные данные: В первой строке записано нечётное число K — количество групп избирателей (1 ≤ K ≤ 101). Во второй строке через пробел записаны K нечётных чисел, которые задают количество избирателей в группах. Население острова не превосходит 9999 человек.
Выходные данные: Выведите минимальное количество сторонников партии,
способное решить исход голосования.
Пример№1: Пример№2:
входные данные | выходные данные |
3 5 7 5 | 6 |
Алгоритм решения:
Объявляется вектор неопределенной длины
Внимание! Разные типы данных.
Для получения дробного значения: x =(float) b/4; // x=1.75
Вывод два знака после запятой: printf("%0.2f",k);
Вариант №1 Задача №2: Очередь в школьный буфет
Во время перерыва у дверей буфета выстроилась очередь из n школьников (1 ≤ n ≤ 10^5). Каждый из вновь подходивших школьников либо вставал в конец очереди, либо умудрялся встать в начало очереди. В итоге, к моменту открытия буфета, номер прихода школьника и его номер в очереди могли не совпадать. Требуется вывести для каждого школьника в очереди к моменту открытия буфета, число, соответствующее номеру его прихода. Очередь формируется по следующему правилу: если k-е число последовательности равно 0, то школьник вставал в конец очереди, если 1, то в начало. Например: дана последовательность из 4 чисел {1 1 0 1}. Сначала 1-й станет 1-м {1}, далее 2-й станет 1-м {2 1}, 3-й станет последним {2 1 3}, 4-й станет 1-м {4 2 1 3}.
4
1 1 0 1
==> 4 2 1 3
Вар. №1 Задача №2: Очередь в школьный буфет
Во время перерыва у дверей буфета выстроилась очередь из n школьников (1 ≤ n ≤ 10^5). Каждый из вновь подходивших школьников либо вставал в конец очереди, либо умудрялся встать в начало очереди. В итоге, к моменту открытия буфета, номер прихода школьника и его номер в очереди могли не совпадать. Требуется вывести для каждого школьника в очереди к моменту открытия буфета, число, соответствующее номеру его прихода. Очередь формируется по следующему правилу: если k-е число последовательности равно 0, то школьник вставал в конец очереди, если 1, то в начало. Например: дана последовательность из 4 чисел {1 1 0 1}. Сначала 1-й станет 1-м {1}, далее 2-й станет 1-м {2 1}, 3-й станет последним {2 1 3}, 4-й станет 1-м {4 2 1 3}.
4
1 1 0 1
==> 4 2 1 3
#include <bits/stdc++.h>
using namespace std;
int main() {
int i,n,a;
cin>>n;
vector <int> v;
for (i=1; i<=n; i++){
cin>>a;
if(a==0)v.insert(v.end(),i);
else v.insert(v.begin(),i);}
for (i=0; i<v.size(); i++)
cout<<v[i]<<" ";
}
Вариант №2 Задача №3:
Для заданной последовательности n целых чисел необходимо найти максимальную сумму её элементов, номера которых различаются строго на 5 (в последовательности рассматриваются только пары таких элементов, например: [0] - [5], [1] - [6]...). Значение каждого элемента последовательности из отрезка [1; 1000]. Количество элементов последовательности не превышает 1000000. Для решения данной задачи разрешается использовать только вектор не более 5 элементов. Например:
8
1 2 3 4 5 6 7 8
==> 11
Вариант №2 Задача №3:
Для заданной последовательности n целых чисел необходимо найти максимальную сумму её элементов, номера которых различаются строго на 5 (в последовательности рассматриваются только пары таких элементов, например: [0] - [5], [1] - [6]...). Значение каждого элемента последовательности из отрезка [1; 1000]. Количество элементов последовательности не превышает 1000000. Для решения данной задачи разрешается использовать только вектор не более 5 элементов. Например:
8
1 2 3 4 5 6 7 8
==> 11
#include <bits/stdc++.h>
using namespace std;
int main(){
vector <int> v(5);
int n,a,i,m=0;
cin>>n;
for (int i=0; i<5; i++) cin>>v[i];
for (int i=5; i<n; i++) {
cin>>a;
if (a+v[0]>m)m=a+v[0];
v.erase(v.begin());
v.push_back(a); }
cout<<m;
}
Вариант №3 Задача №2:
Объявить вектор без размера, добавить в вектор n элементов и заполнить его натуральными числами (n и значения всех элементов вектора вводится с клавиатуры). Произвести циклический сдвиг влево на k элементов. Например: первоначальное расположение 9 элементов в векторе {1 3 5 7 9 11 13 15 17}. После циклического сдвига влево на два элемента (k=2) вектор будет иметь следующее расположение элементов {5 7 9 11 13 15 17 1 3}.
9 2
1 3 5 7 9 11 13 15 17
==> 5 7 9 11 13 15 17 1 3
Вариант №3 Задача №2:
Объявить вектор без размера, добавить в вектор n элементов и заполнить его натуральными числами (n и значения всех элементов вектора вводится с клавиатуры). Произвести циклический сдвиг влево на k элементов. Например: первоначальное расположение 9 элементов в векторе {1 3 5 7 9 11 13 15 17}. После циклического сдвига влево на два элемента (k=2) вектор будет иметь следующее расположение элементов {5 7 9 11 13 15 17 1 3}.
9 2
1 3 5 7 9 11 13 15 17
==> 5 7 9 11 13 15 17 1 3
#include <bits/stdc++.h>
using namespace std;
int main() {
int i,n,t,k;
cin>>n>>k;
vector <int> v(n);
for (i=0; i<n; i++) cin>>v[i];
for (i=0; i<k; i++){
t=v[0];
v.erase(v.begin());
v.push_back(t);}
for (i=0; i<v.size(); i++)cout<<v[i]<<" ";
}
Вариант №4 Задача №4:
Дана последовательность n положительных целых чисел, все числа не превышают 10000. Количество n из отрезка [4; 200] только четное. Отсортировать элементы последовательности, следующим образом: первую половину по возрастанию, вторую по убыванию. Например: последовательность 12 элементов {17 2 3 4 15 6 7 8 9 10 11 12}. После сортировки последовательность будет иметь следующее расположение элементов {2 3 4 6 15 17 12 11 10 9 8 7}. Разрешается завести вектор или два вектора по половинкам, отсортировать элементы используя команду sort.
12
17 2 3 4 15 6 7 8 9 10 11 12
==> 2 3 4 6 15 17 12 11 10 9 8 7
Вариант №4 Задача №4:
Дана последовательность n положительных целых чисел, все числа не превышают 10000. Количество n из отрезка [4; 200] только четное. Отсортировать элементы последовательности, следующим образом: первую половину по возрастанию, вторую по убыванию. Например: последовательность 12 элементов {17 2 3 4 15 6 7 8 9 10 11 12}. После сортировки последовательность будет иметь следующее расположение элементов {2 3 4 6 15 17 12 11 10 9 8 7}. Разрешается завести вектор или два вектора по половинкам, отсортировать элементы используя команду sort.
12
17 2 3 4 15 6 7 8 9 10 11 12
==> 2 3 4 6 15 17 12 11 10 9 8 7
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,i,j,k,b,a,l;
vector <int> v, v2;
cin>>n;
for (i=0;i<n;i++) {
cin>>b;
if (i<n/2) v.push_back(b);
else v2.push_back(b);
}
sort (v.begin(),v.end());
sort (v2.rbegin(),v2.rend());
for (i=0;i<n/2;i++) {cout<<v[i]<<" ";}
for (j=0;j<n/2;j++) {cout<<v2[j]<<" ";}
}