主页 / 问题 / 640208
Accepted
Nikcet
Asked:2020-03-16 17:48:11 +0000 UTC2020-03-16 17:48:11 +0000 UTC

挑战 Codility。数学[关闭]

  • 772

有一个班级，一排有 N 个学生。您需要给学生拍照，但出于审美原因，您希望他们按身高顺序排列。为此，您可以告诉相邻的一组学生改变他们的位置。您的目标是找到站在相邻组中的最少学生人数，在重新排列他们的位置后，将导致整行按身高排序。

学生的当前位置由数组A给出，其中元素A K记录位置K学生的身高。排列后，学生应按身高非递减顺序排序。那些。A P ≤ A P+1对于任何 0 ≤ P < N-1。

例如，如果数组 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，并返回相邻组中站立的学生的最小数量，排序后将对整个数组进行排序。如果学生数组已经排序，函数应该返回 0。

例如，对于上述数组 A，该函数应返回 3。

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

我想看看你的解决方案，最好是在 JS 中（我正在学习它）。

javascript

1 个回答

  1. Best Answer

    第一个想法 - 愚蠢地在额头上 - 我们排序; 您正在寻找的范围是在未排序和排序数组的第一个和最后一个不匹配之间......但那是 O(n log n) + O(n) 内存。虽然次数n最多10万已经很少了。

    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
    • 0

相关问题