ABC246D 2-variable Function Solution
目录更好的阅读体验戳此进入
题面
存在函数 $ f(a, b) = a^3 + a^2b + ab^2 + b^3 $,要求 $ a, b \ge 0 $,给定 $ n $,求最小的 $ f(a, b) $ 满足 $ f(a, b) \ge n \(。\) n \le 10^{18} $。
Solution
显然 $ a, b $ 的范围不超过 $ 10^6 $,则可以枚举 $ a $,二分 $ b $,取最小值即可。
对于二分 $ b $ 的单调性证明,可以考虑固定 $ a $ 为参数,则有函数 $ f(b) = b^3 + ab^2 + a^2b + a^3 $,三次函数不好操作,所以考虑求导,显然 $ f'(b) = 3b^2 + 2ab + a^2 $,因为 $ a, b $ 非负,所以显然导函数 $ f'(b) \ge 0 $,所以范围内函数取值单调递增,于是可以二分。
或者不进行二分,根据单调性,显然 $ a $ 减小时 $ b $ 不会比上次更大,所以写个双指针枚举,$ a $ 升序,$ b $ 降序,小于 $ n $ 时直接 break
即可。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template<typename T = int>
inline T read(void);
ll Func(int a, int b){return (ll)a * a * a + (ll)a * a * b + (ll) a * b * b + (ll)b * b * b;}
int main(){
ll N = read<ll>();
ll mn(LLONG_MAX);
for(int x = 0; x <= (int)1e6; ++x){
int l = 0, r = (int)1e6;
ll cur(-1);
while(l <= r){
int mid = (l + r) >> 1;
ll tmp = Func(x, mid);
if(tmp >= N)cur = tmp, r = mid - 1;
else l = mid + 1;
}
mn = min(mn, cur);
}printf("%lld\n", mn);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_10_21 初稿
标签:Function,return,int,题解,ll,ret,variable,void,define From: https://www.cnblogs.com/tsawke/p/16820302.html