Catch the theives 题解

· · 题解

题目

这道题挺简单的，怎么才74个AC?

废话不多说，讲一下思路：

题目给出合法的四元组的数量 n,求最小的 m。

那么我们就可以二分 m 了，用 check 来枚举。

可是，题目可能有多个 m 满足 check(m)=n。我们需要找出最小的。

别急,把 check(m)<n 的最大 m+1 不就行了么？

代码来了！

#include<iostream>
#define int long long//基本操作 
using namespace std;
int check(int x){
    int sum=0;
    for(int i=2;i*i*i<=x;i++)sum+=x/(i*i*i);
    return sum;//返回sum 
}
signed main(){//main返回signed也是可以的 
    int n,l=1,r=5000000000000000,ans;
    cin>>n;
    while(l<=r){//二分答案 
        int mid=(l+r)/2;
        if(check(mid)<n)ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<(check(ans+1)==n?ans+1:-1);//三目运算(格式:表达式1?成立时执行:不成立时执行;) 
    return 0;//Wonderful!
}//区区19行代码!

Bye!