Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2011-12-14 22:28:34

kiberok
Новий користувач
Зареєстрований: 2011-10-27
Повідомлень: 23

Re: Sorting

MrOlimp написав:

Серед задач другого туру є й ще легша=) З кодом у дві строки.

Да-да)

Поза форумом

 

#27 2011-12-15 11:49:15

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 338
Вебсайт

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 карточки местами.smile

Поза форумом

 

#29 2011-12-28 17:59:09

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: Sorting

Може краще було б, все-таки, в окремій темі рішення викладати, щоб відокремити обговорення задач та рішень?

Поза форумом

 

#30 2011-12-28 18:02:10

il____
Новий користувач
Зареєстрований: 2011-12-08
Повідомлень: 10

Re: Sorting

Можна обговорити рішення вокремій темі:)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt