1
根据题意,我们逐天模拟,第 iii 天就在累计上加上 iii 直到累计超过 kkk,最后输出最后一天的日期即可。时间复杂度 O(N)O(N)O(N),可以通过此题数据范围。
2
根据等差序列求和公式,前 nnn 天可以收到的经验值为 ∑i=1ni\sum\limits_{i=1}^nii=1∑n i,即为 n(n+1)2\dfrac{n(n+1)}22n(n+1) 。配合二分答案,check 的时间复杂度为 O(1)O(1)O(1),二分的时间复杂度为 O(logN)O(\log N)O(logN),我们实现了 O(logN)O(\log N)O(logN) 的时间复杂度,可以通过 long long 数据范围。
3
我们发现,我们要求的就是关于 nnn 的不等式 n(n+1)2≥k\dfrac{n(n+1)}2\geq k2n(n+1) ≥k 的最小整数解。解得:
n≥12(8k+1−1)andn≤12(−8k+1−1)n\geq\dfrac 12(\sqrt{8k+1}-1)\quad\text{and}\quad n\leq\dfrac 12(-\sqrt{8k+1}-1) n≥21 (8k+1 −1)andn≤21 (−8k+1 −1)
后者为负解集,舍去。答案即为 ⌈12(8k+1−1)⌉\lceil\dfrac 12(\sqrt{8k+1}-1)\rceil⌈21 (8k+1 −1)⌉。时间复杂度 O(1)O(1)O(1),配合高精度,可以通过极大的数据范围。