Интервью Вопрос... Попытка разобраться, но не могла получить эффективное решение

Ответ 1

Предлагаю следующий алгоритм:
 1. Сначала рассмотрите все C[ i ] как пустые гнезда.
 2. Для каждого i, где B[ i ] = 0, положим C[ i ] = A[ i ]
 3. Перейдите через массив слева направо, и для каждого i, где B[ i ] = -1 положите
C[ j ] = A[ i ], где 0 <= j < i - это наименьший индекс, для которого C[ j ] по-прежнему пуст. Если такой индекс не существует, ответ невозможен.
 4. Перейдите через массив справа налево, и для каждого i, где B[ i ] = 1 положите
C[ j ] = A[ i ], где i < j < n является наибольшим индекс, для которого C[ j ] по-прежнему пуст. Если такой индекс не существует, ответ невозможен.

Почему мы помещаем A [i] в ​​крайнее левое положение на шаге 2? Ну, мы знаем, что мы должны поместить его в некоторую позицию j < я. С другой стороны, если положить его влево, мы увеличим наши изменения, чтобы не застрять на шаге 3. См. Этот пример для иллюстрации:

A: [ 1, 2, 3 ]
B: [ 1, 1,-1 ]

Изначально C пуст: C:[ _, _, _ ]
  У нас нет 0-s, поэтому переходим к шагу 2.
  Нам нужно выбрать, разместить элемент A[ 2 ] до C[ 0 ] или C[ 1 ].
  Если мы поместим его не влево, мы получим следующую ситуацию:
  C: [ _, 3, _ ]
  И... Ой, мы не можем организовать элементы A[ 0 ] и A[ 1 ] из-за недостаточного места:(
Но, если мы поместим A [2] влево, мы получим
C: [ 3, _, _ ] И вполне возможно завершить алгоритм с помощью
C: [ 3, 1, 2 ]:)

Сложность:
Мы делаем три раза по массиву, поэтому сложность O(3n) = O(n) - linear.

Дополнительный пример:

A: [ 1, 2, 3 ]
B: [ 1, -1, -1 ]

Пройдите шаг за шагом по алгоритму:
1. C: [ _, _, _ ]
2. Пустой, потому что нет 0-s в B
3. Поместите A[ 1 ] и A[ 2 ] в крайние левые позиции:

C: [ 2, 3, _ ]

4. Поместите A[ 0 ] в крайнее правое свободное (в этом примере единственное) свободное место:

C: [ 2, 3, 1 ]

Каков ответ.

Исходный код:

#include <iostream>
#include <string>
#include <vector>

using namespace std;


vector< int > a;
vector< int > b;
vector< int > c;
int n;

bool solve ()
{
    int i;
    for( i = 0; i < n; ++i )
        c[ i ] = -1;
    for( i = 0; i < n; ++i )
        if( b[ i ] == 0 )
            c[ i ] = a[ i ];
    int leftmost = 0;
    for( i = 0; i < n; ++i )
        if( b[ i ] == -1 )
        {
            for( ; leftmost < i && c[ leftmost ] != -1; ++leftmost ); // finding the leftmost free cell
            if( leftmost >= i )
                return false; // not found
            c[ leftmost++ ] = a[ i ];
        }
    int rightmost = n - 1;
    for( i = n - 1; i >= 0; --i )
        if( b[ i ] == 1 )
        {
            for( ; rightmost > i && c[ rightmost ] != -1; --rightmost ); // finding the rightmost free cell
            if( rightmost <= i )
                return false; // not found;
            c[ rightmost-- ] = a[ i ];
        }
    return true;
}


int main ()
{
    cin >> n;
    a.resize(n);
    b.resize(n);
    c.resize(n);
    int i;
    for( i = 0; i < n; ++i )
        cin >> a[ i ];
    for( i = 0; i < n; ++i )
        cin >> b[ i ];
    if( !solve() )
        cout << "Impossible";
    else
        for( i = 0; i < n; ++i )
            cout << c[ i ] << ' ';
    cout << endl;
    return 0;
}

Ответ 2

Слишком много времени потрачено:; -)

#include <stdint.h>
#include <string.h>
#include <stdio.h>
static int doit(int A[], int B[], int C[], size_t size)
{
    size_t first_free = size - 1;
    size_t last_free = 0;
    for (size_t i = 0; i < size; ++i) {
        if (B[i]) {
            if (i < first_free) {
                first_free = i;
            }
            if (i >= last_free) {
                last_free = i;
            }
        }
    }
    for (int i = 0; i < size; ++i) {
        if (B[i] < 0) {
            if (first_free >= i) {
                return 0;
            }
            C[first_free] = A[i];
            first_free = i;
        } else if (B[i] == 0) {
            C[i] = A[i];
        }
    }
    for (int i = size - 1; i >= 0; --i) {
        if (B[i] > 0) {
            if (last_free <= i) {
                return 0;
            }
            C[last_free] = A[i];
            last_free = i;
        }
    }
    return 1;
}
int a[] = { 1, 2, 3 };
int b[] = { 1, -1, -1 };
int c[sizeof(a) / sizeof(int)];
int main(int argc, char **argv)
{
    if (!doit(a, b, c, sizeof(a) / sizeof(int))) {
        printf("no solution");
    } else {
        for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
            printf("c[%zu] = %d\n", i, c[i]);
    }
}

Ответ 3

Это можно свести к сетевому потоку. Вот как построить гаджет:

• Для каждого элемента я из A создайте node a_i и добавьте ребро емкости единицы из источника в a_i.

• Для каждого элемента я из C создайте node c_i и добавьте ребро емкости единицы из c_i в приемник.

• Для всех 0 значений в B с индексом я добавьте ребро от a_i до c_i, снова с единичной емкостью.

• Для всех значений -1 в B с индексом я добавьте ребро от a_j до c_i, где 0 <= j < я.

• Для всех 1 в B с индексом я добавьте ребро от a_j до c_i, где я < j < п.

Пример гаджета:

   a_0 *----* c_0
      / \    \
     /   \    \
    /     |    \
   /  a_1 | c_1 \
S *----*  | *----* T
   \    \ \/    /
    \    \/\   /
     \   /\ | /
      \ /  \|/
       *    *
      a_2   c_2


  B = [ 0, 1, -1]

Максимальный поток в этой сети с емкостью = n соответствует присваиванию от a до c. Чтобы получить перестановку, просто вычислите минимальный разрез сети.

Ответ 4

Здесь есть решение с одним внешним проходом. Поскольку i идет от 0 до n-1, j переходит в n-1 в 0. Индексы l и r указывают на первое доступное пятно "flex" (где b[i] != 0). Если в любой точке l проходит r, тогда свободных пятен нет, и в следующий раз b[i] != 0 внешний цикл будет прерываться преждевременно с помощью "нет решения".

Казалось бы, это было точно, но если это произойдет в некоторых случаях, добавление еще нескольких условий для циклов, которые продвигают индексы flex, должно быть достаточным для его исправления.

Будет выполняться постороннее присваивание (когда b[i] == 0, c будет установлено как i, так и j), но это безопасно. (То же самое касается проверки l > r.)

#include <stdio.h>

#define EMPTY 0 

int main()
{
  int a[] = {1, 2, 3};
  int b[] = {1, -1, -1};
  int c[] = {EMPTY, EMPTY, EMPTY};

  int n = sizeof(a) / sizeof(int);

  int l = 0, r = n - 1;
  int i, j;

  /* Work from both ends at once.
   *   i = 0 .. n-1
   *   j = n-1 .. 0
   *   l = left most free "flex" (c[i] != 0)  slot
   *   r = right most free flex slot
   *
   *   if (l > r) then there are no more free flex spots
   *
   *   when going right with i, check for -1 values
   *   when going left with j, check for 1 values
   *   ... but only after checking for 0 values
   */

  for (i = 0, j = n - 1; i < n; ++i, --j)
  {
    /* checking i from left to right... */
    if (b[i] == 0)
    {
      c[i] = a[i];

      /* advance l to the next free spot */
      while (l <= i && c[l] != EMPTY) ++l;
    }
    else if (b[i] == -1)
    {
      if (i <= l) break;

      c[l] = a[i];

      /* advance l to the next free spot, 
       * skipping over anything already set by c[i] = 0 */
      do ++l; while (l <= i && c[l] != EMPTY);
    }

    /* checking j from right to left... */
    if (b[j] == 0)
    {
      c[j] = a[j];
      while (r >= j && c[r] != EMPTY) --r;
    }
    else if (b[j] == 1)
    {
      if (j >= r) break;

      c[r] = a[j];
      do --r; while (r >= j && c[r] != EMPTY);
    }

    if (l > r)
    {
      /* there cannot be any more free flex spots, so
         advance l,r to the end points. */
      l = n;
      r = -1;
    }
  }

  if (i < n)
    printf("Unsolvable");
  else
  {
    for (i = 0; i < n; ++i)
      printf("%d ", c[i]);
  }

  printf("\n");

  return 0;
}