ARC084 B Small Multiple 题解

原题链接

Description

给定一整数 \(k\) , 求一个 \(k\) 整数倍的数 \(x\) ，使得 \(x\) 的数位累加和最小，输出最小的累加和。

Solution

这道题简单但值得一想。

正着枚举每一个 \(k\) 整数倍的数 \(x\) 肯定会超时，反过来考虑，可以找一个数 \(x\) 使其为 \(k\) 的倍数，那么对于每个数 \(x\) ，均有以下两种操作：

• 将这个数 \(\times 10\) ，对应花费为 \(0\)

• 将这个数 \(+ 1\) ，对应花费为 \(1\)

至于说为什么可以转化为这两种操作，主要是一种贪心的思想，我们并不需要考虑 \(x\) 的大小，只需要尽量使其花费最小。

实现就很简单了，这里可以使用 \(01BFS\) ，将使用花费为 \(0\) 操作所得的数插入队首，将花费为 \(1\) 的插入队尾，注意跳掉已经找过余数相同数的数。

Code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 100100
//#define int long long
int Read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}return x*f;
}
int k,vis[MAXN];
deque<pair<int,int> > q;
int main()
{k=Read();q.push_front(make_pair(1,1));while(!q.empty()){pair<int,int> qwq=q.front();q.pop_front();if(vis[qwq.first]) continue;vis[qwq.first]=1;if(!qwq.first) return printf("%d",qwq.second),0;q.push_front(make_pair(qwq.first*10%k,qwq.second));q.push_back(make_pair((qwq.first+1)%k,qwq.second+1));}
}