题意: 有两个整数序列 a = [a1, a2, ..., an],b = [b1, b2, ..., bn], 长度都为 n, 找到一个最小的数 x, 使得 a 的每个数增加 x 之后对 m 取模, 然后重新排序序列 a, 使得 a == b
原题链接: Modulo Equality https://codeforces.com/contest/1269/problem/B
输入: n,m, 序列长度和模数 m, 第二行是 a1,a2,...,an, 第三行是 b1,b2,...,bn
输出: 最小的 x
分析: 枚举 x, 导致时间复杂度很大, 我在做的时候超时了...
换一种思路, 让时间复杂度降低, 因为我们每个数字 a 加了一个数 x 后对 m 取模后都对应着 0 ~ m - 1 之间的数, 我们可以枚举数字差, 这样时间复杂度会大幅度降低,
我们枚举序列 a 的每个数字, 去对应序列 b 中的 b[0], 因为 b[0] 会对应序列 a 中的某个数字, 我们枚举序列 a, 然后相减, 对 m 取模, 得到 x, 然后对序列 a 的每个数字增加 x,
排完序后, 检查 a == b 是否相等, 然后找到最小的 x...
// 话说为什么 x = abs((b[0] - a[i]) % m) 不可以? 有没有好心的网友告诉我, 只能增加偏移量 m 再相减...
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int INF = 0x3f3f3f3f;
- int main()
- {
- vector<int> a, b;
- int n, m;
- scanf("%d%d", &n, &m);
- a.resize(n), b.resize(n);
- for (int i = 0; i <n; ++i)
- {
- scanf("%d", &a[i]);
- }
- for (int i = 0; i < n; ++i)
- {
- scanf("%d", &b[i]);
- }
- sort(b.begin(), b.end());
- int minx = INF;
- for (int i = 0; i < n; ++i)
- {
- int x;
- if (b[0]>= a[i])
- {
- x = b[0] - a[i];
- }
- else {
- x = m + b[0] - a[i];
- }
- vector<int> c(a);
- for (int j = 0; j < n; ++j) c[j] = (c[j] + x) % m;
- sort(c.begin(), c.end());
- if (c == b)
- {
- minx = min(minx, x);
- }
- }
- printf("%d\n", minx);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3346786.html