Форум программистов, компьютерный форум CyberForum.ru

Сдвиг перестановки. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
18.05.2011, 18:22     Сдвиг перестановки. #1
Сдвиг перестановки
(Время: 1 сек. Память: 16 Мб Сложность: 24%)

Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ... , pn, где каждое 1 <= pi <= n. Будем говорить, что перестановка q1, q2, ... , qn лексикографически меньше перестановки p1, p2, . . . , pn, если существует такое i, что qi < pi, а для любого j < i pj = qj .

Циклическим сдвигом на k перестановки p1, p2, ... , pn называется последовательность, pk+1, pk+2, ... , pn, p1, ... , pk. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданной перестановки.
Входные данные

Первая строка входного файла INPUT.TXT содержит порядок n (1 <= n <= 10^5) заданной перестановки. Вторая строка содержит числа p1, p2, ... , pn, отделенные друг от друга пробелами.
Выходные данные

В выходной файл OUTPUT.TXT выведите перестановку, являющуюся наименьшим лексикографически циклическим сдвигом перестановки, заданной во входном файле.
Пример
INPUT.TXT
3
3 2 1
OUTPUT.TXT
1 3 2
Думал алгоритм решения таков : находим минимальный элемент ставим его на первое место и сдвигаем последовательность. Но такое решение только прошло 9 тестов, кому интересно вот реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream> 
using namespace std; 
const int size = 100001;
int main() {
    freopen("INPUT.TXT", "r", stdin);
    freopen("OUTPUT.TXT", "w", stdout);
    int n, a[size];
    cin >> n;
    for(int i = 0; i < n; ++i) 
        cin >> a[i];    
    int min = a[0];
    for(int i = 1; i < n; ++i) 
        if(a[i] < min) 
            min = a[i]; 
    cout << min << " ";
    for(int i = 0; i < n; ++i) 
        if(a[i] != min) 
            cout << a[i] << " ";
    return 0;
}
Добавлено через 2 часа 52 минуты
Все Я сдаюсь, хз что там не так(((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 18:22     Сдвиг перестановки.
Посмотрите здесь:

C++ перестановки в С++
Перестановки из n чисел C++
Перестановки C++
Инверсии и перестановки C++
C++ те же перестановки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.05.2011, 02:18     Сдвиг перестановки. #2
Цитата Сообщение от Temirlan90 Посмотреть сообщение
Думал алгоритм решения таков : находим минимальный элемент ставим его на первое место и сдвигаем последовательность.
Алгоритм правильный, а вот реализация не очень. Сдвига не увидел вообще. После отыскания минимального элемента, нужно:
- записать в файл сам минимальный элемент
- затем записать в файл элементы следующие за миниальным
- затем записать в файл элементы, которые находятся перед минимальным.

Смысл задачи был такой, что сдвиг не простой а циклический.
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
21.05.2011, 10:35  [ТС]     Сдвиг перестановки. #3
Теперь суть понятно=), сижу уже битые 2 часа и не могу написать код=(
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.05.2011, 10:54     Сдвиг перестановки. #4
Чего здесь писать-то..
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
int a[99999];
int n,min=99999,p;
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    std::cin >> n;
    for (int i = 0; i < n; i++){
        std::cin >> a[i];
        if (min > a[i]) {min=a[i]; p=i;}
    }
    std::cout << a[p] << ' ';
    for (int i=p+1; i < n; i++)
        std::cout << a[i] << ' ';
    for (int i=0; i<p; i++)
        std::cout << a[i] << ' ';
    return 0;
}

Просто при считывании находим наименьший элемент, и другой переменной (допустим р) присваиваем его индекс.
Сначала выводим array[p], затем array[p+1..n-1], затем array[0..p-1]
Как-то так
Yandex
Объявления
21.05.2011, 10:54     Сдвиг перестановки.
Ответ Создать тему
Опции темы

Текущее время: 16:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru