链接:https://ac.nowcoder.com/acm/contest/60393/B 来源:牛客网 氧气少年最近喜欢上了一。 氧气少年有一个文本输入框,最初文本输入框里只有一个字符 ` 1 1'。 氧气少年每次可以进行下面的操作: 选中文本输入框中的部分或全部字符,将选中的字符复制到剪贴板,然后立即将复制的内容粘贴到文本输入框末尾。 现在氧气少年想让文本输入框中恰好有 � n 个 ` 1 1',请求出他需要做的最少的操作次数。 输入描述: 第一行包含一个整数 � ( 1 ≤ � ≤ 2 ⋅ 1 0 5 ) T(1≤T≤2⋅10 5 ),表示测试用例的组数。 对于每组测试用例: 仅输入一行,包含一个整数 � ( 1 ≤ � ≤ 1 0 9 ) n(1≤n≤10 9 )。
时间: 2024-04-16 14:25:38 浏览: 21
根据您提供的链接,问题的描述是让氧气少年通过复制和粘贴操作,将文本输入框中的字符 "1" 复制粘贴到文本输入框中,使得文本输入框中的字符数为 n,求最少的操作次数。
这个问题可以用贪心算法来解决。每次操作时,我们将当前文本输入框中的字符复制并粘贴到末尾,相当于将当前字符数翻倍。因此,我们可以通过不断将字符数逼近 n,每次选择当前字符数的最大倍数作为下一次操作的复制粘贴次数。
以下是一个示例的解决方案:
```c
#include <stdio.h>
int minOperations(int n) {
int count = 0;
int curr = 1;
while (curr < n) {
if (n % curr == 0) {
// 如果当前字符数是 n 的因子,则可以通过复制粘贴直接得到 n 个字符
count += 2; // 复制和粘贴操作各计数一次
curr *= 2; // 更新当前字符数
}
else {
// 如果当前字符数不是 n 的因子,则需要通过多次复制粘贴操作来逼近 n
int factor = n / curr; // 当前字符数与 n 的商,即下一次操作的复制粘贴次数
count += factor + 1; // 复制操作计数一次,粘贴操作计数 factor 次
curr *= factor; // 更新当前字符数
}
}
return count;
}
int main() {
int T; // 测试用例的组数
scanf("%d", &T);
while (T--) {
int n; // 目标字符数
scanf("%d", &n);
int operations = minOperations(n);
printf("%d\n", operations);
}
return 0;
}
```
在这个示例中,我们使用了 `minOperations()` 函数来计算最少的操作次数。通过不断更新当前字符数 `curr`,并根据是否是 `n` 的因子来选择复制和粘贴的次数,最终得到最少的操作次数。
希望这个示例能帮助到您理解问题的解决方法。如果有任何疑问,请随时提问。