题目描述

$N$ 个人均匀地围坐在一个圆桌上，其中 $N$ 是偶数。

座位顺时针依次编号为 $1$ ∼ $N$ 。

每个人头上都带着一个帽子，帽子上有一个数字。

第 $i$ 个座位上的人的帽子编号为 $H_{i}$ 。

每个人都看着自己正对面（直径对面）的人。

请你计算，一共有多少人满足：自己正对面的人戴的帽子的编号和自己戴的帽子的编号相同。

输入格式

第一行包含整数 $N$ 。

接下来 $N$ 行，其中第 $i$ 行包含 $H_{i}$ 。

输出格式

一个整数，表示自己正对面的人戴的帽子的编号和自己戴的帽子的编号相同的人。

样例

样例输入#1

4
0
1
0
1

样例输出#1

4

样例输入#2

4
1
0
0
1

样例输出#2

0

数据范围与约定

$2 \leq N \leq 10^{6}$ ， $0 \leq H_{i} \leq 2 \times 10^{6}$ 。

思路

解决本体的关键是如何找到一个人对面的人的下标。

因为 $2 \mid N$ ，那么每一个人的位置的对面一定对应另一个人的位置，而不是两个人的位置的中间。

对于两个正对面的位置，这两个位置的下标之差为 $\dfrac{1}{2}N$ 。

用数组 $h$ 表示下标为 $i$ 的人的帽子编号。当 $i \in \left [1, \dfrac{1}{2}N \right ]$ 时，下标为 $i$ 的人对面的人的下标为 $i + \dfrac{1}{2}N$ 。为了比较他们的帽子编号是否相同，则只需要比较 $h \left [i \right ]$ 和 $h \left [i + \dfrac{1}{2}N \right ]$ 的大小：

if (h[i] == h[i + n / 2])
{
    ans += 2;
}

还需要注意的是，在结束遍历前 $\dfrac{1}{2}N$ 个人后，在判断一个人的帽子下标是否与对面的人的帽子下标是否相同时也同时判断了对应的后 $\dfrac{1}{2}N$ 个人的帽子的下标。因此，只需要遍历前 $\dfrac{1}{2}N$ 个人，且如果两个人帽子下标相同，则给最终结果加上 $2$ 。

C++

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, ans;
int h[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }

    for (int i = 1; i <= n / 2; i++)
    {
        if (h[i] == h[i + n / 2])
        {
            ans += 2;
        }
    }

    cout << ans << endl;

    return 0;
}