Я пытаюсь практиковать решение проблемы с 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. Я получил чтобы знать, что я должен использовать жадный подход, но не могу сказать. Может ли кто-нибудь помочь мне в этом?минимальное количество действий, необходимых для сортировки массива
ответ
Мы можем видеть, что для сортировки массива каждый элемент нужно только перемещать. не более один.
Итак, чтобы минимизировать количество перемещений, нам нужно найти максимальное количество элементов, которые не перемещаются. И этот элемент является длиной последовательной последовательной последовательностью, которая представляет собой последовательность (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
.
Thankyou Pham Trung это правильно. Не могли бы вы объяснить более ясно? вы говорите, что решение (n - самая длинная непрерывная подпоследовательность)? –
@ RiderForest да. Что еще вы не понимаете? –
Я пытаюсь понять эти строки «longest [data [i]] = longest [data [i] - 1] + 1;" и "result = max (самый длинный [данные [i]], результат); –
Я решил эту проблему на 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));
Надежда, что помогает!
Я думаю, вам стоит попробовать быстро сортировать. –
@art - Я не думаю, что quicksort всегда вернет минимальное количество необходимых ходов. –
Возможный дубликат [Минимальное количество «вставок» для сортировки массива] (http: // stackoverflow.com/questions/20392743/the-minimum-number-of-insertions-to-sort-a-array) –