Tokitsukaze and Function
原题链接
TAG：数学，二分，均值不等式
思路
对 \(f(x)\) 进行求导可以得出 \(f(x)\) 在 \(x=\sqrt{n}\) 处取到最小值，但不确定是 \(\left\lfloor \sqrt{n} \right\rfloor\) 还是 \(\left\lceil \sqrt{n} \right\rceil\) 处。
我们可以分别求出 \(f(\left\lfloor \sqrt{n} \right\rfloor),f(\left\lceil \sqrt{n} \right\rceil),f(l),f(r)\) 进行排序，求得最小的 \(f(x)\)。
令 \(f(t')\) 为最小的 \(f(x)\)，现在求最小的 \(t\)。显然在 \([1,t']\) 的区间内 \(f\) 是单调递减的，因此我们可以在 \([L,t']\) 的范围内进行二分查找出最小的 t。时间复杂度为 \(O(T\cdot\log{n})\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | #include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve() {
LL n, l, r;
cin >> n >> l >> r;
LL mn = n / l + l - 1;
LL p = l;
if (n / r + r - 1 < mn) {
mn = n / r + r - 1;
p = r;
}
LL x = sqrt(n);
if (l <= x && x <= r && n / x + x - 1 < mn) {
mn = n / x + x - 1;
p = x;
}
x++;
if (l <= x && x <= r && n / x + x - 1 < mn) {
mn = n / x + x - 1;
p = x;
}
LL lo = l, hi = p;
while (lo < hi) {
LL mid = lo + hi >> 1;
if (n / mid + mid - 1 == mn) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|