2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83 [2021/05/23 09:52] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83 [2021/05/23 10:01] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 83: | 行 83: | ||
| 记本次 $\text{pop}$ 的元素为 $a_{k+1}$。则队列二的当前所有元素一定是由 $a_t-b$ 得到的，由于 $a_t\gt a_{k+1}$，所以 $a_t-b\gt a_{k+1}-b$，满足单调性。 | 记本次 $\text{pop}$ 的元素为 $a_{k+1}$。则队列二的当前所有元素一定是由 $a_t-b$ 得到的，由于 $a_t\gt a_{k+1}$，所以 $a_t-b\gt a_{k+1}-b$，满足单调性。 | ||
| - | 于是总时间复杂度 $O(k)$。 | + | 于是总时间复杂度 $O(k)$。另外假定 $a\gt b$，可以考虑二分答案，然后枚举 $n$，然后统计 $m$，时间复杂度 $O(\sqrt k\log (ab))$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛83.1621734727.txt.gz · 最后更改: 2021/05/23 09:52 由 jxm2001
