Печать страницы

TransformArray
Преобразование массивов (уровень 1).
оригинал тут (http://www.topcoder.com/stat?c=problem_statement&pm=6692&rd=10792)

Очки за задачу: 250
Кол-во присланных решений / кол-во участников 61 / 73 (83.56%)
Количество решений прошедших все тесты / общее количество решений 47 / 61 (77.05%)

Постановка задачи:
У нас есть массив положительных чисел. Мы должны преобразовать этот массив повторяя одну и ту же оперцию, покане останется менее двух элементов в массиве:

1) выбрать два элемента, которые имеют минимальную абсолютную разницу. Если таких пар несколько, то выбрать пару, чья сумма элементов минимальна. Если все равно осталось несколько пар, то выбрать любую.
2) уменьшить значение элементов выбранной пары на 1.
3) удалить нулевые элементы массива.

Легко заметить, что процесс конечен за фиксированное кол-во шагов.
Например, имеем массив из 4 элементов {3, 2, 3, 2}. Процесс преобразования будет происходить следующим образом:
Step 1: (3, 2, 3, 2) --> (3, 1, 3, 1) (уменьшаем элементы 2 и 2)

Step 2: (3, 1, 3, 1) --> (3, 3) (очередное уменьшение значений элементов делает их равными 0 и 0, удаляем их)

Step 3: (3, 3) --> (2, 2)

Step 4: (2, 2) --> (1, 1)

Step 5: (1, 1) --> ()

Получили пустой массив.

В программе мы получаем int[] которые представляют трансфоруемый массив. Необходимо вернуть количество шагов преобразования. Реализацию алгоритма произвести в методе класса:

class TransformArray {
public:
int doTransform(vector <int>);
};

Ограничения:
- размер массива от 1 до 50.
- каждый элемент может принимать значения от 1 до 1000.

Примеры:

- {3,2,3,2}
ответ: 5

- {3}
ответ: 0
Мы уже имеем 1 элемент в массиве, поэтому трансформация не требуется.

- {1,2,3,4}
ответ: 4
Трансформация должна пройти следующим образом:
{1, 2, 3, 4} --> {1, 3, 4} --> {1, 2, 3} --> {1, 3} --> {2}

- {10,6,3,7,7,9,5,1,8,4}
ответ: 27

Решение:

Т.к. ограничений в задаче мало, то она может быть решена простым перебором. Достаточно лишь делать то, что требуется. Наибольшую сложность в этой задаче представляет то, что требуется на каждом шаге выбирать пару с минимальной разницей элементов и минимальной суммой элементов.
Лучшим решением признано решение (http://www.topcoder.com/tc?module=HSProblemSolution&cr=22378820&rd=10792&pm=6692) кодера RuslanSM (http://www.topcoder.com/tc?module=MemberProfile&cr=22378820&tab=alg).

Код: (cpp)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TransformArray {
public:
  int doTransform(vector <int>);
};

int TransformArray::doTransform(vector <int> elements) {
  int ans=0;
  while (true)
  {
    int minn=100000;
    int minx=100000;
    int mini,minj;
    for(int i=0;i<elements.size();i++)
    {
      for(int j=i+1;j<elements.size();j++)
      {
        if (i!=j &&
           elements[i]!=0 && 
           elements[j]!=0 && 
           ((abs(elements[i]-elements[j])<minn) || (abs(elements[i]-elements[j])==minn && elements[i]+elements[j]<minx)) )
        {
          minn=abs(elements[i]-elements[j]);
          minx=elements[i]+elements[j];
          mini=i;
          minj=j;
        }
      }
    }
    if (minn!=100000)
    {
      elements[mini]--;
      elements[minj]--;
    } else break;
    ans++;
  }
  return ans;
}

КИТА unofficial

Ваши интересы => Задачи с TopCoder => Тема начата: vimmax от Ноябрь 20, 2007, 12:33:53