Вся проблема сводится к поиску наибольшего элемента из шести, у вас есть попытка 4 + 6/2 = 7.Для более чем шести элементов с каждой попыткой вы сортируете два из них (что вы и сделали), поэтому формула 4 + N/2 исходит из ...
Первые пять тестов (на самом деле,все, что нам нужно / можно сделать) будет:
(6) 12345 34 // one of 1235 must be heavier than 34
(5) 12346 34 // one of 1236 must be heavier than 34
(4) 12356 35 // ...
(3) 12456 45
(2) 13456 45
(1) 23456 45
Пока мы можем быть уверены, что 3, 4 и 5 не могут быть самыми тяжелыми, оставаясь 1, 2, 6
Теперь давайтевнимательно рассмотрим:
Удаление 5 или 6 из результатов набора дважды в одном и том же 3-м и 4-м.Удаление 4 из установленных результатов приводит к тому, что 3-я и 4-я комбинации встречаются только один раз.Удаление 1, 2 или 3 из результатов набора трижды в одном и том же 3-м и 4-м.
Нас сейчас интересуют именно эти два набора с одинаковыми 3-м и 4-м, встречающимися дважды:
1, 2, 3, 4, 5 и 1, 2, 3, 4, 6. Из них мы знаем, что 5 или 6 должны быть самыми большими;в сочетании с самым первым наблюдением (за исключением 3, 4, 5) остается только 6.
На самом деле, мы даже знаем больше:
Не выбранное (5) из набора двух вхождений(5, 6) является вторым самым тяжелым, единственное вхождение 3/4-го (4) показывает третий самый тяжелый, а оставшийся (3) из первоначально исключенных (3, 4, 5) является четвертым самым тяжелым.
Только 5-е и 6-е нельзя различить ...
Редактировать: Фильтрация избыточных значений:
Вы можете немного упростить свой код:
int t;
std::cin >> t;
while(t--) // sparse you another variable...
{
int n = 12;
--n; // exclude highest value!
int ar[] = {1, 2, 3, 4, 5}; // just *always* maintain the values in the array...
// note: the array is one larger as you had initially!
for (int i = 6; i < n; i = i + 2) // prefer local scope for i!
// ^ can start at a later point of time, we'll be replacing AFTERWARDS
{
std::cout << '?';
for(auto a : ar) // loop might or not be more elegant
std::cout << '\t' << a; // performance: most likely, compiler unrolls
// anyway...
std::cout << std::endl;
int x, y; // scope as local as possible...
std::cin >> x >> y;
// OK, I don't want to modify the loop variable, so I now use a duplicate...
int ii = i;
for(auto& a : ar) // I like the range based for loops...
// ^ reference this time is important, though!
{
if(a == x || a == y)
a = ii++;
}
}
if((n & 1) == 0)
{
// for even n, we have done one test too few!
// instead of duplicating the code, you might write a common function for...
std::cout << '?';
for(auto a : ar)
std::cout << '\t' << a;
std::cout << std::endl;
int x, y; // scope as local as possible...
std::cin >> x >> y;
for(auto& a : ar)
{
if(a == x || a == y)
{
a = n;
break; // just replace one!!!
}
}
}
}
Приведенный выше код даст 5 элементов для проверки.Помните, что мы исключили наибольшее значение (--n;)?Теперь мы вернемся:
++n;
n теперь будет шестым проверяемым значением в дополнение к пяти оставшимся в массиве (если вы не любите увеличивать и уменьшать, выальтернативно может поддерживать две переменные, конечно).Вы можете использовать std::swap для обмена одним значением массива за другим.
Примечание: лично я предпочел бы больше C ++ - например, std::array<int, 5> ar({1, 2, 3, 4, 5}); вместо необработанного массива, но это не большая проблема,Тем не менее, это облегчило бы передачу массива, если вы создадите его из дубликата кода:
void f(std::array<int, 5> const& ar); // or non-const, if you want to replace inside, too
// or in more generic form:
template <size_t N>
void f(std::array<int, N> const& ar);
// vs.:
void f(int const(&ar)[5]);
// the more generic form:
template <size_t N>
void f(int const(&ar)[N]);
// or classical (and better known) pointer variant:
void f(int const* ar, size_t length);
Заключительные примечания:
- Вы не проверяете потоки послепользовательский ввод.Если пользователь вводит что-либо invlid, это нарушит ваши потоки и, следовательно, весь код.В этом конкретном случае это может быть необязательным, но в целом было бы неплохо привыкнуть с самого начала (что-то вроде
if(!cin >> x >> y) { /* appropriate error handling */ }), возможно, даже позже проверить допустимый диапазон (например, ошибка, если x и y равны или не совпадают ровно с одним значением в массиве - для последнего нам следует обратить внимание на несоответствие с уже замененным значением). - Насколько яПонял вопрос, отрицательные значения не имеют смысла, поэтому я бы (последовательно) предпочел
unsigned int как тип данных.Но это не большая проблема, так что решайте сами ...