Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#26 2011-12-14 22:28:34
- kiberok
- Новий користувач
- Зареєстрований: 2011-10-27
- Повідомлень: 23
Re: Sorting
MrOlimp написав:
Серед задач другого туру є й ще легша=) З кодом у дві строки.
Да-да)
Поза форумом
#27 2011-12-15 11:49:15
Re: Sorting
"Измерять продуктивность программирования подсчетом строк кода — это так же, как оценивать постройку самолета по его весу".
— Bill Gates
Відредаговано LVV (2011-12-15 11:49:37)
Вік живи - вік навчайся.
Поза форумом
#28 2011-12-28 17:53:50
- il____
- Новий користувач
- Зареєстрований: 2011-12-08
- Повідомлень: 10
Re: Sorting
Думаю, можно уже писать решение.
Вот:
Код:
# include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector < int > lnk,mas;
lnk.resize(n+1);
mas.resize(n+1);
int p,k=0;
for (int i=1;i<=n;i++){cin>>p;lnk[p]=i;mas[i]=p;}
for (int i=1;i+1<=n;i++) if (lnk[i]!=i)
{
k++;
p=mas[lnk[i]];
mas[lnk[i]]=mas[i];
lnk[mas[i]]=lnk[i];
mas[i]=p;
lnk[i]=i;
}
cout<<k<<endl;
return 0;
}Идея такова:
Когда меняем карточки, то для оптимального варианта нужно что бы за 1 ход как минимум 1 карточка стала на свое место.
Идем по массиву, если карточка не на своем месте, то находим где она должна быть (массив lnk) и меняем те 2 карточки местами.
Поза форумом
#30 2011-12-28 18:02:10
- il____
- Новий користувач
- Зареєстрований: 2011-12-08
- Повідомлень: 10
Re: Sorting
Можна обговорити рішення вокремій темі:)
Поза форумом