1 条题解

  • 0
    @ 2024-11-27 14:03:09

    因为Monster是懒狗,所以题解也很水。

    对于公式(hours[i]+hours[j])%24=0(hours[i] + hours[j]) \% 24 = 0,运用取模的性质即可得到(hours[i]%24+hours[j]%24)%24=0(hours[i] \% 24 + hours[j] \% 24) \% 24 = 0

    因此对于每个hours[i]hours[i]我们都用其对24取模,这样可以将数组的每一项都映射到一个大小为24的哈希表中,然后遍历hourshours数组的同时对哈希表更新维护,即可以求解数对数量。

    时间复杂度O(n)O(n),空间复杂度O(24)O(24)

    代码

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    int main()
    {
        ll n, ans = 0;
        cin >> n;
        vector<int> hours(n), Hash(24, 0);
        for (int i = 0; i < n; i++)
        {
            cin >> hours[i];
            ans += Hash[(24 - hours[i] % 24) % 24];
            Hash[hours[i] % 24]++;
        }
        cout << ans << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    236
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    79
    已通过
    14
    上传者