题解 CF1311D 【Three Integers】
ShineEternal
2020-02-26 07:50:39
[更佳的阅读效果。](https://blog.csdn.net/kkkksc03/article/details/104505461)
## description:
- 给定你三个数 $a,b,c$ ,保证 $a\le b\le c$。
- 一次操作中,你可以将任何一个数 $+1$ 或者 $-1$ 。
- 问你最少要用多少次操作,可以使得 $a$ 是 $b$ 的因数, $b$ 是 $c$ 的因数。
- **多组数据**,数据组数不大于 $100$,$1\le a,b,c\le 10^4$。
- 先输出最少的操作次数,再输出最终的方案。(方案如果有多组可输出任意一组。)
## solution:
我们发现中间的数 $b$ 是一个与其他两个数都有直接关系的数,所以考虑对 $b$ 进行枚举。
观察数据范围,我们枚举到 $1.5\times 10^4$ 就够了。
然后我们枚举每一个 $b$ 的所有因数,每一个 $b$ 的所有倍数,找到最少的操作次数即可。
## code:
```cpp
#include<cstdio>
#include<cmath>
using namespace std;
int Abs(int x)
{
if(x<0)return -x;
return x;
}
int Min(int x,int y)
{
if(x<y)return x;
return y;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int aa,b,c;
scanf("%d%d%d",&aa,&b,&c);
int AAA,BBB,CCC;
int sum=0x3f3f3f3f;
for(int i=1;i<=15000;i++)
{
int ans=0;
int Zuo,You;
int tmp=0x3f3f3f3f;
int qaq=sqrt(i);
ans=Abs(b-i);
for(int j=1;j<=qaq;j++)
{
if(i%j!=0)
{
continue;
}
if(Abs(aa-j)<tmp)
{
tmp=Abs(aa-j);
Zuo=j;
}
if(Abs(aa-(i/j))<tmp)
{
tmp=Abs(aa-(i/j));
Zuo=i/j;
}
}
ans+=tmp;
tmp=0x3f3f3f3f;
for(int j=i;j<=32000;j+=i)
{
if(Abs(c-j)<tmp)
{
You=j;
tmp=Abs(c-j);
}
}
ans+=tmp;
if(ans<sum)
{
sum=ans;
AAA=Zuo;
BBB=i;
CCC=You;
}
}
printf("%d\n",sum);
printf("%d %d %d\n",AAA,BBB,CCC);
}
return 0;
}
```