Codeforces Round 674 (Div. 3) 解题报告

CF1426C Increase and Copy

Codeforces Round 674 (Div. 3) 第三题,签到题。

题意翻译

初始给你一个元素 \( 1 \),每次操作你可以选择让一个元素 \( + 1 \) 或者复制一个元素。

求最少需要多少次操作使其总和不小于 \( n \)。

题解

显然可以发现,最快增长到 \( n \) 的方案一定是先不断 \( + 1 \) 到一个数 \( x \),然后再复制 \( x \) 的 \( y – 1 \) 遍,最后总和为 \( x y \geq n \)。总的操作次数为 \( x + \left\lceil \frac { n } { x } \right\rceil – 1 \)。

显然 \( x=\sqrt { n } \) 时操作次数取最小值。

#include <bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{ //快读
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

int n;

int main(void)
{
    reg int t = read(); //读入数据组数 t
    while (t--)
    {
        n = read();                                   //读入 n
        reg int r = sqrt(n);                          //求平方根
        printf("%d\n", r + n / r - 2 + (n % r != 0)); //直接输出答案
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8