минимальное количество действий, необходимых для сортировки массива

Question

Я пытаюсь практиковать решение проблемы с Codeforces. Это сортировать массив, перемещая элементы массива либо в начало, либо до конца массива. Сначала я думал, что это самая длинная подпоследовательность, но в некоторых случаях она не работает. Например, если вход 4,1,2,5,3, то LIS равен 3, но ответ на проблему переместит 4 в конец массива, а затем 5 в конец массива, который дает нам 2. Также i пытался опробовать на примере 1,6,4,5,9,8,7,3,2 в этом LIS 1,4,5,9, но ответ на проблему составляет 7 шагов между 1 и 2. Я получил чтобы знать, что я должен использовать жадный подход, но не могу сказать. Может ли кто-нибудь помочь мне в этом?

Answer 1

Мы можем видеть, что для сортировки массива каждый элемент нужно только перемещать. не более один.

Итак, чтобы минимизировать количество перемещений, нам нужно найти максимальное количество элементов, которые не перемещаются. И этот элемент является длиной последовательной последовательной последовательностью, которая представляет собой последовательность (a0, a1, ... an) с a(i + 1) = ai + 1.

Например,

(4,1,2,5,3), длинная непрерывная последовательность (1,2,3)

(5,2,1,3,4), длинная непрерывная последовательность (2,3,4)

Таким образом, мы имеем наш код:

int[]longest = new int[n + 1]; 
int result = 0; 
for(int i = 0; i < n; i++){ 
    longest[data[i]] = longest[data[i] - 1] + 1; 
    result = max (longest[data[i]] , result); 
} 

print "Minimum number of move is " + (n - result) 

Пояснение:

В коде я использую массив longest, индекс которого ith хранит самую длинную непрерывную последовательность, которая заканчивается на value i.

Итак, мы можем видеть, что longest[i] = longest[i - 1] + 1.

И результат для самой длинной непрерывной последовательности - это максимальное значение, сохраненное в массиве longest.

Answer 2

Я решил эту проблему на Codeforces во время самого конкурса. Хорошая проблема.

Think «самая длинная непрерывная подпоследовательность». Ответ: n-самая длинная непрерывная подпоследовательность.
Пример: Возьмите 1 2 3 7 5 6 4. Самая длинная непрерывная подпоследовательность 1 2 3 4. Теперь вы можете перемещать оставшиеся элементы в определенном порядке, чтобы получить отсортированный массив всегда. По крайней мере, как я думал об этом интуитивно

Вот отрывок из основного кода:

int n=in.readInt(); 
    int[] a=new int[n+1]; 
    int[] cnt=new int[n+1]; 
    int max=0; 
    for(int i=0;i<n;i++) 
     a[i]=in.readInt(); 
    for(int i=0;i<n;i++) 
    { 
     cnt[a[i]]=1+cnt[a[i]-1]; 
     max=Math.max(max,cnt[a[i]]); 
    } 
    out.printLine((n-max)); 

Надежда, что помогает!