题解 | #和移位#

F

一个优化查询的算法，用于找到最佳的旋转偏移量 给定一个数组 a 和多个查询 x，对于每个查询，需要找到一个偏移量 k，使得

• 将数组循环右移 k 个位置
• 计算 a[i] + a[(i+k)%n] 的和等于 x 的对数最多
• 如果有多个 k 得到相同的最多对数，选择最小的 k

unordered_map<int, pair<int,int>> best;
// best[x] = {最佳k, 出现次数}

对于每个可能的偏移量 k (0 ≤ k < n)

1. 统计所有位置 i 的 a[i] + a[(i+k)%n] 的和
2. 使用 cnt 映射记录每个和值出现的次数
3. 更新 best 映射：
   • 如果当前和值 s 的出现次数更多
   • 次数相同但 k 更小
   • 则更新为当前的 k 对于每个查询 x

• 如果 x 在 best 中存在，输出对应的最佳 k
• 否则输出 0

算法复杂度

• 预处理：O(n²) - 对每个k遍历整个数组
• 查询：O(q) - 每个查询O(1)查找

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    unordered_map<int, pair<int,int>> best;
    for (int k = 0; k < n; k++) {
        unordered_map<int,int> cnt;
        for (int i = 0; i < n; i++) {
            int s = a[i] + a[(i + k) % n];
            cnt[s]++;
        }
        for (auto &[s, c] : cnt) {
            auto it = best.find(s);
            if (it == best.end() || c > it->second.second || (c == it->second.second && k < it->second.first)) {
                best[s] = {k, c};
            }
        }
    }
    while (q--) {
        long long x;
        cin >> x;
        if (best.count(x)) cout << best[x].first << "\n";
        else cout << 0 << "\n";
    }
}