Задача с Codility. Математика. Помогите решить.? [требует правки]

399

16 марта 2017, 22:19

В ряд стоит класс из N учеников. Нужно сфотографировать студентов, но по эстетическим соображениям вы хотите, чтобы они были упорядочены в порядке роста. Чтобы достичь этого, вы можете указать смежной группе студентов изменить свои позиции. Ваша цель состоит в том, чтобы найти минимальное количество студентов, стоящих в смежной группе, которые после перестановки своих позиций приведут к тому, что весь ряд будет упорядочен по высоте.

Текущее расположение учащихся задается массивом A с нулевой индексацией длины N, в котором элемент A[K] записывает высоту ученика в позиции K. После перестановки ученики должны быть отсортированы в неубывающем порядке высоты. Т.е. A[P]<=A[P+1] для любого 0<=P

Например, если массив A имеет следующий вид:

A [0] = 1
A [1] = 2
A [2] = 6
A [3] = 5
A [4] = 5
A [5] = 8
A [6] = 9

То наименьшая группа студентов, которую нужно переставить, - это A [2..4], длины 3. После перегруппировки этой группы получим [1,2,5,5,6,8,9], которая находится в правильном порядке . Любая другая перестановка, включающая смежную группу из менее чем трех студентов, не приведет к правильной сортировке результирующей строки.

Напишите решение функциональной функции (A) {}, которое задает массив с нулевым индексом A, описывающий строку N студента, возвращает минимальное число студентов, стоящих в смежной группе, которая при перестановке вызывает упорядочение всей строки по высоте . Если строка студентов уже правильно, функция должна вернуть 0.

Например, для описанного выше массива A функция должна возвращать 3.

Предположим, что:
 1. N - целое число в диапазоне [1. 100 000]
 2. каждый элемент массива А является целым числом в диапазоне [1. 100 000 000].

Нужно, в общем-то, само решение. Но будет круто, если еще на JS напишите. C++ в метки поставил, потому что лучше его понимаю(пока) и смогу перевести его в JS. Наверное.

За ранее спасибо.

Answer 1

Первая мысль - тупо в лоб - сортируем; искомый диапазон - между первым и последним несовпадениями неотсортированного и отсортированного массива... Но это - O(n log n) + память O(n). Хотя раз n до 100000 - это очень немного.

Код на C++:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    constexpr int N = 100000;
    vector<int> A(N);
    for(size_t i = 0; i < N; ++i)
        A[i] = rand();
    for(int i = rand(); i >= 0; --i)
        A[i] = i;
    for(int i = N - rand(); i < N; ++i)
        A[i] = i;
    vector<int> B(A);
    sort(B.begin(),B.end());
    int b, e;
    for(b = 0; b < N && A[b]==B[b]; ++b);
    if (b == N) { cout << "0\n"; return 0; }
    for(e = N-1; e >= 0 && A[e]==B[e]; --e);
    cout << (e-b+1) << "\n";
}

Ну, чтоб реально посмотреть-проверить - вот:

int main()
{
    srand(time(0));
    constexpr int N = 10;
    vector<int> A(N);
    for(size_t i = 0; i < N; ++i)
        A[i] = rand()%10;
    for(int i = rand()%4; i >= 0; --i)
        A[i] = i;
    for(int i = N - rand()%4; i < N; ++i)
        A[i] = i;
    vector<int> B(A);
    sort(B.begin(),B.end());
    int b, e;
    for(b = 0; b < N && A[b]==B[b]; ++b);
    if (b == N) { cout << "0\n"; return 0; }
    for(e = N-1; e >= 0 && A[e]==B[e]; --e);
    cout << (e-b+1) << "\n";
    for(auto i: A) cout << i << " "; cout << endl;
    for(auto i: B) cout << i << " "; cout << endl;
}

Получаются результаты вроде

7
0 1 5 6 6 4 1 5 1 9 
0 1 1 1 4 5 5 6 6 9

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Заменить один div на другой с условием

Есть один div вывода цены:

353

javascript

Не могу вывести связанную модель

Здравствуйте! Ситуация следующая:

297

jQuery

Проверка на уже существующий email PHP + jQuery

Здравствуйте! Есть форма: https://jsfiddlenet/pkhyLvcc/

341

jQuery

Связать PHP и запуск действия через JS

Здравствуйте

310