B. Cow and Friend

时间:2022-01-24 17:19:13

题目链接:https://codeforces.com/contest/1307/problem/B.

分析:我们设最大的喜爱的数为y,假设y > x,我们可以构造一个三角形,两边之和大于第三边,那么就只要跳两步。这是情况1。
我们再考虑第二种情况,y < x时,我们可以在之前平铺y,再最后构造一个等腰三角形,两边都是y,假设之前平铺的y使用n步,最后跳了2步构造了一个等腰三角形,我们如何求出(n 2)呢?
我们来推一下,我们可以得到n * y p = d,而我们尽可能地想让n小,那么p就要尽可能地大,那么p最大可以是多少呢?那么最好的结果就是尽量靠近2 * y,那我们可以让p取到p ~ 2p之间,这是最好的结果,这样n = d / y - p / y = d / y - 1,然后我们可以算出结果d / y - 1 2 = ceil(d / y)。这个上取整就是这样推出来的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100005;
int a[N];
int main()
{
    int t;
    scanf("%d", &t);

    while (t--)
    {
        int n, x;
        scanf("%d%d", &n, &x);

        int m = 0;
        bool flag = false;
        for (int i = 1; i <= n;   i)
        {
            scanf("%d", &a[i]);
            if (a[i] == x) flag = true;
            m = max(m, a[i]);
        }

        if (flag)
        {
            puts("1");
        }
        else
        {
            if (m > x)
            {
                puts("2");
            }
            else
            {
                printf("%dn", (x   m - 1) / m);
            }
        }
    }


    return 0;
}