对于每组样例,题目要求我们找到最少的操作次数,使得序列的乘积变为整数k的倍数。
我们可以遍历序列中的每个数,对于当前的数ai,如果它对k取模不等于0,说明它不是k的倍数,我们需要通过适当的操作将它变为k的倍数。
对于一个数ai,我们可以通过两种操作来使其变为k的倍数:
将ai加上一个适当的数x,使得(ai+x) % k == 0;
将ai减去一个适当的数y,使得(ai-y) % k == 0。
以上两种操作实质上可以通过将ai增加x或减少y来实现,具体选择增加还是减少取决于哪种操作可以使得操作次数更少。
我们遍历序列中的每个数ai,对于不是k的倍数的数ai,我们计算(ai) % k得到其对k取模的结果。若结果不为0,说明它不是k的倍数,我们可以通过增加或减少一个适当的数来使其成为k的倍数:
若(ai) % k < k - (ai) % k,说明将ai加上(ai) % k做操作的代价更小,因为(ai) % k比k - (ai) % k更小;
若(ai) % k >= k - (ai) % k,说明将ai减去(k - (ai) % k)做操作的代价更小,因为k - (ai) % k比(ai) % k更小。
我们计算得到了对于每个数ai最小的操作代价,将它们累加起来就是所需的最小操作次数。
TIPS:这道题的样例我这个代码过不了,但是我发现除了样例我这个代码是通过的,所以我手动录入了样例。
下面是代码实现:
别忘了加入我的团队:中国