f884 - 柏恩的奶茶
題目描述
題目描述了柏恩喝奶茶的情景，他每天喝四杯奶茶，且每杯奶茶的甜度必須比前一杯多 1 或相同。給定柏恩喝完奶茶後的心情值，要求計算四杯奶茶的甜度。
解題思路
題目要求找到四個連續整數，使得它們的乘積加上 1 等於給定的心情值。由於心情值範圍較大，直接枚舉不可行。可以利用二分搜尋法來尋找中間的甜度值，然後計算其他三杯奶茶的甜度，並驗證乘積是否等於給定的心情值。由於甜度必須是正整數，因此二分搜尋的範圍可以設定為 1 到 65536。
複雜度分析
- 時間複雜度: O(log N)，其中 N 是二分搜尋的上限 (65536)。
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
//2^64 18446744073709551616
//2^63 9223372036854775808
unsigned long long int n,ans;
__int128 bs(__int128 l,__int128 r){
if(l>r)return r;
__int128 m=(l+r)/2,v=m*m*m*m;
if(v>n)
return bs(l,m-1);
else
return bs(m+1,r);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
ans=bs(1,65536);
cout << ans-1 << " " << ans << " " << ans+1 << " " << ans+2 << "\n";
}
}