首页 > 试题广场 >

小A弹吉他

[编程题]小A弹吉他

热度指数：3268 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小 A 不想成为不被需要的人，所以她决定要努力练习吉他。但是她现在被一个作业题卡着了，为了珍惜练习时间，她现在向你求助。

$\hspace{15pt}$ 对于给定的正整数 $m$ ，小 A 需要选一个正整数 $n$ ，并构造一个长度为 $n$ 的正整数序列 $\{a_1,a_2,\dots,a_n\}$ 使得它们的和等于 $m$ 。
$\hspace{15pt}$ 小 A 想知道，对于所有可能的构造，令 $t_i$ 表示 $a_1,a_2,\dots,a_n$ 中等于 $i$ 的元素个数，最大的 $\operatorname{mex}\big\{t_1,t_2,\dots,t_{114^{514}}\big\}$ 是多少。请你求出这个值。

$\hspace{15pt}$ 本题有多组数据，请你对每组数据的 $m$ 都求出相应的结果。

$\hspace{15pt}$ 整数序列的 $\operatorname{mex}$ 定义为没有出现在序列中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入一个正整数  代表规定的数组和。

输出描述:

对于每一组测试数据，在单独的一行上输出一个整数，表示最大的  。

示例1

输入

输出

2
3
4

说明

对于第一组数据，其唯一可能的构造是选取  且 ，这样 ，因此 。
对于第二组数据，其中一种可能的构造是选取  且 ，这样 ，因此 。可以证明这是更优的。

算法知识视频讲解

Yui___

#include <iostream>

bool check(long long x,long long m)
{
    if(x <= 1)
    {
        return true;
    }
    
    long long cost = ((x-1) * x * (x+1)) / 6;

    return cost <= m;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 0;
    std::cin>>t;
    while(t--)
    {
        long long m = 0LL;
        std::cin>>m;

        long long left = 1LL, right = 2000000LL;
        long long ans = 0LL;

        while(left <= right)
        {
            int mid = left + ((right - left) >> 1);

            if(check(mid,m))
            {
                ans = mid;
                left = mid + 1;
            }
            else
            {
                right = mid -1;
            }
        }
        
        std::cout<<ans<<'\n';
    }
    
}

发表于 2025-11-22 15:05:36 回复(0)

提交观点

问题信息

难度：

1条回答 9收藏 7浏览

小A弹吉他

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题