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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
#1

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

18.05.2011, 18:22. Просмотров 1838. Ответов 3
Метки нет (Все метки)

Сдвиг перестановки
(Время: 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++
Вот опять задачка на перестановки, если кому интересно, или кому просто не трудно сделать, буду очень признателен! Заранее огромное...

перестановки в С++ - C++
Поменять местами элементы с четными и нечетными номерами

Перестановки - C++
Даны символы, например ABCDEF, и число n. Нужно вывести все возможные комбинации перестановок этих символов по n. Максимальное число...

Перестановки - C++
Есть число которое складается из нулей и единиц. C клавиатуры вводится N - общее количество цифр и K - количество единиц. Найти и вивести...

Перестановки с next_permutation - C++
Есть входные данные 9-12 цифр надо из них создать все возможные перестановки и отправить их в вектор. Задумка do { ...

Двойные перестановки - C++
Здравствуйте программисты.Нужна ваша помощь. Помогите написать программу простенькую, на C++ : двойные перестановки n1*m1 + n2*m2 Буду...

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

Смысл задачи был такой, что сдвиг не простой а циклический.
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
21.05.2011, 10:35  [ТС]     Сдвиг перестановки. #3
Теперь суть понятно=), сижу уже битые 2 часа и не могу написать код=(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.05.2011, 10:54     Сдвиг перестановки.
Еще ссылки по теме:

Перестановки из n чисел - C++
Не получается написать функцию, которая сохраняет всевозможные перестановки из n элементов в двухмерный массив int arr, где len-число...

перестановки с повторениями! - C++
Помогите! есть прога все считает правильно только не выводит значения с повторениями! помогите исправить! // mat_kkursa.cpp:...

Перестановки без i - C++
Есть рекурсивная функция ,генерирующая перестановки.Требуется,чтобы на i месте(p) не стоял i.Причем проверять это надо не при...

Инверсии и перестановки - C++
Ребят, помогите пожалуйста, сделать 2 задачки, буду очень вам признателен! Заранее огромное спасибо. 1.Дана перестановка. Наименьшее...

Номер перестановки - C++
Надо написать программу которая выдаёт номер перестановки, и при етом не генерирует сами перестановки.

Метод одиночной перестановки - C++
Пример: Исходный текст: Неясное становятся еще более не понятным. Ключ: ЛУНАТИК Л У Н А Т И К | А И К Л Н Т У 4 7 5 1...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 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     Сдвиг перестановки.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru