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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Линейный двусвязный список http://www.cyberforum.ru/cpp-beginners/thread298700.html
Список задан структурой struct *node { char info; node *prev; node *next; }; и была введена некоторая последовательность чисел. Нужно расположить элементы списка в обратном порядке не применяя копирования. Натолкните на мысль или примерный алгоритм подскажите)
C++ Функция передачи команды в cmd.exe Добрый день/вечер/утро, товарищи программисты! Мне бы хотелось написать программу (точнее, жалкое её подобие), которая бы открывала командную строку, записывала бы туда команду, ну... скажем "cd C:\\Program Files\\bla-bla-bla" и командная строка бы, её выполнила. На самом деле, нужно записать не cd, но я думаю, что смысл понят ;) Результат работы: запускаешь exe проги -> появляется командная... http://www.cyberforum.ru/cpp-beginners/thread298687.html
C++ Матрицы и файлы
Задача во вложении. Люди помогите решить, заранее благодарен :)
C++ Выполнить упорядочивание каждого столбца матрицы по возрастанию
Задачки по фунциям и массивам. все во вложении. прошу помощи.
C++ Замена и смена элементов матрицы http://www.cyberforum.ru/cpp-beginners/thread298680.html
Суть задачи во вложении. Буду очень признателен за помощь.
C++ Дано целое число. Вывести элементы последовательности. Вычислить сумму ряда не используя стандартных функций Вобщем суть задачи заключена во вложении, помогите пожалуйста решить. подробнее

Показать сообщение отдельно
Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333

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

18.05.2011, 18:22. Просмотров 1751. Ответов 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 минуты
Все Я сдаюсь, хз что там не так(((
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 06:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru