【练习】栗酱的不等式
栗酱的不等式
https://ac.nowcoder.com/acm/problem/14696
题目
题目描述：有不等式y⋅x3≤ n，已知y为正整数，x为大于1的正整数，问当x和y的解数量刚好为m的时候n的最小值，如果不存在输出 -1。
输入描述：
多组数据读入。每组数据一个数字m，如题所示。
输出描述：
每组数据输出一行，输出答案。
解析
1）知识点
- 这道题是一道二分的题目。
2）看题目
- 首先看题，就是说我们给定解的数量，求最小的n。
3）算法分析
- 我们求解，首先写成函数的形式y = n / x3。
- 然后用二分法查找答案，假设答案是mid，那么我们要统计mid有多少种解，就设定一个循环，让x从2到n（范围题目有）进行累加。
- 如果统计数量比想要的多，就删右界。少就删左界。如果正好相等，就表示和题目说的一样，数量刚好为m，就标记答案就好了。
4）算法操作
- 首先就是经典的二分模板：
while (l <= r) { ll mid = l + r >> 1; if (judge(mid)) { r = mid - 1; } else l = mid + 1; } - 然后和上面说的一样，我们要对答案进行统计：
ll judge(ll x) { ll cnt = 0; for (ll i = 2; i * i * i <= x; i++) cnt += x / (i * i * i); //求出y的组数 return cnt; } - 我们这里用函数进行统计，所以在外面进行判断，同时标记答案：
ll cnt = judge(mid); if (cnt >= n) { r = mid - 1; if (cnt == n) ans = mid; } else l = mid + 1; - 就按此进行二分就好了，因为答案不符合要求就要输出-1，那么把ans初始化为-1就好了（不符合要求就不会改变）。
5）打代码
- 首先就是多组输入。
- 然后开始按照上面讲的二分。
- 下面全代码~
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const ll INF = 0x3f3f3f3f3f3f3f3f;
//全局变量区
ll judge(ll x) {
ll cnt = 0;
for (ll i = 2; i * i * i <= x; i++)
cnt += x / (i * i * i);
//求出y的组数
return cnt;
}
//函数预定义区
int main() {
IOS;
ll n;
while (cin >> n) {
ll ans = -1, l = 8, r = INF;
while (l <= r) {
ll mid = l + r >> 1;
ll cnt = judge(mid);
if (cnt >= n) {
r = mid - 1;
if (cnt == n) ans = mid;
}
else l = mid + 1;
}
cout << ans << endl;
}
return 0;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
