【HPUoj】Translate（思维）

FishWang

发布于 2025-08-27 12:09:27

1940

题目链接：点击打开链接

问题 E: Translate

时间限制: 1 Sec 内存限制: 128 MB 提交: 2 解决: 1 状态

题目描述

你N个正整数a[1]...a[N]，在最初的时候，你选择一个正整数X,然后以后每一步，你可以使一个数a[i] 变成 a[i] + X,或者 a[i] - X,聪明的你，一定会知道怎么选择这个X，使得最后所有的数都变成相等，而且使用的变化步数最少。

输入

多组测试数据。对于每组数据，一个N(2 <= N <= 1000),接下来一行有N个数a[1]...a[N] (1 <= a[i] <= 10^6)。

保证这N个数不全相等。

输出

每组数据单独一行，你找出的正整数X，以及最少步数，两个数用一个空格隔开.

样例输入

样例输出

1 2
2 5

大胆的猜测+ 不怕死的WA = AC

刚睡醒就想到这道题，突然想到是不是要变成的数为这些数的中位数，然后想到奇数的情况就是中位数。

如果是偶数，那么是取中间两个数的平均数，还是取左边或右边的数。

想了几个事例后，感觉分别取左边和右边的数找到一个最小的应该是对的。

然后就起床开始打代码了，结果就AC了。

代码如下：

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define LL long long
int n;
int GCD(int a,int b)
{
	return b == 0 ? a : GCD(b,a%b);
}
int solve(int base,int num[],int &g)
{
	int ans = 0;
	g = -1;		//最大公约数
	for (int i = 1 ; i <= n ; i++)
	{
		int t = abs(num[i]-base);
		if (t == 0)
			continue;
		ans += t;
		if (g == -1)
			g = t;
		else
			g = GCD(g,t);
	}
	return ans / g;
}
int main()
{
	int num[1011];
	int ans;
	int base;
	while (~scanf ("%d",&n))
	{
		for (int i = 1 ; i <= n ; i++)
			scanf ("%d",&num[i]);
		sort(num+1,num+1+n);
		int g1,g2;
		if (n & 1)
			ans = solve(num[n/2+1] , num,g1);
		else
//			ans = min(solve(num[n/2],num) , solve(num[n/2+1],num));
		{
			int ans1 = solve(num[n/2],num,g1);
			int ans2 = solve(num[n/2+1],num,g2);
			if (ans1 > ans2)
			{
				ans = ans2; 
				swap(g1,g2);
			}
			else
				ans = ans1;
		}
		printf ("%d %d\n",g1,ans);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int