Ссылка на проблему: здесь
В этой задаче нам дан массив, в котором каждый элемент на позиции обозначает, сколько людей он подкупил, чтобы они пришли на текущую позицию.
Например: в q = [1, 4, 2, 3, 5],
Мы можем сказать, что 1 и 5 никого не подкупили, следовательно, они находятся в исходном положении. Кроме того, 4 подкупил 2 и 3, чтобы добраться до позиции 2.
Также есть условие, что ни один человек не может дать взятку более чем 2 людям.
Чтобы решить эту проблему, нам просто нужно знать, сколько человек подкупил человек, чтобы достичь своего нынешнего положения. Если внимательно присмотреться, эта проблема похожа на задачу подсчета инверсий с условием, что элемент нельзя переместить более чем на 2 позиции от его текущей позиции, что делает ее еще проще.
Подход к решению
Сначала мы начинаем с последнего элемента массива и переходим к первому элементу.
Для каждого элемента массива мы проверяем, смещен он или нет, т.е. (A[i] == i+1) , если он не смещен, мы продолжаем нашу итерацию, иначе мы делаем следующие шаги (для элемента в позиции i массива):
а) если A[i-1] == текущая позиция, т.е. A[i ] подкупил A[i+1], мы добавим 1 к нашему . результат и поменять местами оба элемента.
б) Если A[i-2] == текущей позиции, т.е. A[i] подкупил A[i-1] и A[i-2], мы добавим 2 к наш результат и поменять местами элементы, чтобы они достигли исходного состояния.
Код:
void minimumBribes(vector<int> q) {
int n = q.size();
int result = 0;
for(int i = n - 1; i >= 0; i--) {
if(q[i] != i+1) {
if ((i-1 >= 0) && (q[i-1] == i+1)) {
result += 1;
q[i-1] = q[i];
q[i] = i+1;
} else if((i-2 >= 0) && (q[i-2] == i+1)) {
result += 2;
q[i-2] = q[i-1];
q[i-1] = q[i];
q[i] = i+1;
} else {
cout<<"Too chaotic"<<endl;
return;
}
}
}
cout<<result<<endl;
return;
}
Временная сложность: O(n).
