B.Modulo Equality

2021年09月16日 阅读数:1
这篇文章主要向大家介绍B.Modulo Equality,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题意:有两个整数序列a = [a1, a2, ..., an],b = [b1, b2, ..., bn],长度都为n,找到一个最小的数x,使得a的每一个数增长x以后对m取模,而后从新排序序列a,使得a == bios

原题连接:Modulo Equalityurl

输入:n,m,序列长度和模数m,第二行是a1,a2,...,an,第三行是b1,b2,...,bn 输出:最小的xspa

分析:枚举x,致使时间复杂度很大,我在作的时候超时了... 换一种思路,让时间复杂度下降,由于咱们每一个数字a加了一个数x后对m取模后都对应着0 ~ m - 1之间的数,咱们能够枚举数字差,这样时间复杂度会大幅度下降, 咱们枚举序列a的每一个数字,去对应序列b中的b[0],由于b[0]会对应序列a中的某个数字,咱们枚举序列a,而后相减,对m取模,获得x,而后对序列a的每一个数字增长x, 排完序后,检查a == b是否相等,而后找到最小的x....net

代码以下:code

#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;
}