CF#1288A Deadline （函数求最值问题）

问题描述

题目大意

输入 $n$ 和 $d$ ， 能否找到 $x$ 使得 $x+\lceil \frac{d}{x+1}\rceil \le n,(x\le n)$
如果可以就输出"YES"，否则输出"NO"。

题目解析

这是一道有意思的题目，用上了高中的函数最值问题的求解。

令$f(x)=x+\lceil \frac{d}{x+1}\rceil ,x\le n$

问题就转换为,判断 $f(x{)}_{min}\le n$是否成立。

我们先忽略向上取整符号，只要最后 $f(x)$ 的结果向上取整就可以了。

令$u=x+1,u\le n+1$

于是，$f(u)=u+\frac{d}{u}-1,u\le n+1$

我们对$f(u)$ 求导，得 $f^{{}^{\prime }}(u)=1-\frac{d}{u^2}$

令 $f^{{}^{\prime }}(u)=0$，得 $u=\sqrt{d},x=\sqrt{d}+1$

当$u>\sqrt{d}$ 时, $f^{{}^{\prime }}(u)>0$, $f^{{}^{\prime }}(u)$单调递增。
当$u<\sqrt{d}$ 时, $f^{{}^{\prime }}(u)<0$, $f^{{}^{\prime }}(u)$单调递减。

所以 $x=\sqrt{d}+1$ 时，$f(x)$取得最小值， $f(x{)}_{min}=2\sqrt{d}-1$，只要判断 $2\sqrt{d}-1\le n$是否成立即可。

看似推导过程很长，但是只要是考过高考的人其实也就是两分钟的事情，还好我高中的东西还没有还给老师hhh。

题目代码

/*** Author: Veggie*/ #include <bits/stdc++.h> using namespace std; int T, s, d;//ceil是向上取整函数 int ok(int n, int d) {return ceil(2.0 * sqrt(d) - 1) <= n; } int main() {cin >> T;while(T--) {cin >> n >> d;if (d <= n || ok(n, d))printf("YES\n");elseprintf("NO\n");}return 0; }

总结

以上是生活随笔为你收集整理的CF#1288A Deadline （函数求最值问题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。