Codeforces 1113B Sasha and Magnetic Machines 题解

题目简述

有一个长度为 $n$ 的正整数序列。你可以对这个数列进行最多 $1$ 次的如下操作：

• 选择两个数 $i$ 和 $j$，其中 $1 \leq i,j \leq n$ 并且 $i \neq j$，并选择一个可以整除 $a_i$ 的正整数 $x$，然后将 $a_i$ 变为 $\frac{a_i}{x}$，将 $a_j$ 变为 $a_j \cdot x$。

问你操作后，该序列中所有数的和最小能达到多少。

$2 \leq n \leq 5 \cdot 10^4$，$1 \leq a_i \leq 100$。

题目分析

考虑枚举每一个 $a_i$，由于 $a_i$ 很小，所以可以直接枚举 $a_i$ 的因子 $x$，因为要让操作后的和最小，所以 $a_j$ 一定是序列中除了 $a_i$ 的最小值，维护一个最小值和次小值，如果 $a_i$ 是最小值，那么 $a_j$ 就是次小值，否则 $a_j$ 就是最小值，确定了以上三个值后按照题意更新答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
const int N=5e4+10;
int a[N],Min=N,Min2=N,sum,ans=N*1000,n;
void solve()
{
	cin>>n;
	For(i,1,n)
	{
		cin>>a[i];
		sum+=a[i];
		if(a[i]<Min)
		{
			Min=a[i];
		}
	}
	For(i,1,n)
	{
		if(a[i]>Min&&a[i]<Min2)
		{
			Min2=a[i];
		}
	}
	For(i,1,n)
	{
		int temp=(a[i]==Min?Min2:Min);
		For(j,1,a[i])
		{
			if(a[i]%j==0)
			{
				ans=min(ans,sum-a[i]+a[i]/j+temp*(j-1));
			}
		}
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
	return 0;
}