c++ - 打印最大元素的索引

Question

彼得有 N 个球，编号为 1 到 N。

没有两个球的重量是一样的。你想找到最重的球，但你不知道它是哪一个，而彼得不想直接把它给你。因此，他决定和你一起玩游戏。

你最多可以问 Peter Q=4+N/2 个问题。在每个问题中，您必须给彼得五个不同球的编号，彼得告诉您这些球中第 3 个和第 4 个最重的球的编号。找出最重的球的编号!

互动:首先，您应该阅读包含单个整数 T 的行，该整数 T 表示测试用例的数量。对于每个测试用例，您应该从阅读包含单个整数 N 的一行开始。要提出问题，您应该打印一行包含字符“?”、一个空格和五个以空格分隔的整数 i1、i2、i3、i4 和 i5:五个不同球的编号(以任意顺序)。

然后，您必须读取包含两个空格分隔的整数的行:第 3 和第 4 最重的球的编号。

要完成测试用例的求解，打印一行包含字符“!”、一个空格和一个整数 im:最重的球的数量(1≤im≤N)。

不要忘记在打印每一行后刷新输出!

约束:

• 1≤T≤1,000
• 6≤N≤100

示例:

You               Grader
                  1
                  6
? 1 2 3 4 5
                  3 4
? 1 2 3 4 6
                  3 4
? 1 2 3 5 6
                  3 5
? 1 2 4 5 6
                  4 5
? 1 3 4 5 6
                  4 5
? 2 3 4 5 6
                  4 5
! 6

解释:

球按重量降序排列。

这是对 codechef 竞赛中的一个问题的解释，解释是因为原始问题陈述不是很清楚。

这是我的代码(对于 n>6):

我知道它不是很有效，我一直在编辑它试图找出错误

(C++)

Answer 1

整个问题归结为找到六个中最大的元素，您有 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, 6) 中选择的 (5) 是第二重的，第三/第四次出现的 (4) 显示第三重，而最初排除的其余 (3) ones (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 现在将是第 6 个要检查的值，除了数组中剩余的五个值(如果你不喜欢递增和递减，你可以选择维护两个变量，当然)。您可以使用 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);

最后的旁注:

1. 您不在用户输入后检查流。如果用户输入任何无效内容，这将破坏您的流，从而破坏整个代码。在这种特定情况下可能没有必要，但总的来说，从一开始就习惯是个好主意(比如 if(!cin >> x >> y) { /* appropriate error handling */ } )，甚至可能在之后检查有效范围(例如错误，如果 x 和 y 是等于或不完全匹配数组中的一个值——但对于后者，我们必须注意不要与已经替换的值匹配。
2. 就我对这个问题的理解而言，负值是没有意义的，因此我(始终)更喜欢 unsigned int 作为数据类型。但这不是什么大问题，所以您自己决定...