小数字时间限制1 秒空间限制256 MB知识点模拟网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小娴给阿笙出了一种简单数学题小娴给出数字n nn并规定三种操作若n nn为非负整数开根号向上取整即n → ⌈ n ⌉ n \to \lceil \sqrt{n} \rceiln→⌈n​⌉对当前的数字n nn减1 11即n → n − 1 n \to n - 1n→n−1对当前数字除以2 22向上取整即n → ⌈ n 2 ⌉ n \to \lceil \frac{n}{2} \rceiln→⌈2n​⌉。现在可以对数字n nn操作m mm次小娴想让阿笙计算出操作m mm次之后n nn最小可以为多少。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 2 × 10 5 ) T\ (1 \le T \le 2 \times 10^5)T(1≤T≤2×105)代表数据组数每组测试数据描述如下在一行上输入两个整数n , m ( 1 ≤ n , m ≤ 10 9 ) n, m\ (1 \le n, m \le 10^9)n,m(1≤n,m≤109)代表初始数字、操作次数。输出描述对于每一组测试数据在单独的一行上输出一个整数代表操作m mm次之后n nn最小可以为多少。示例 1输入3 10 1 2 1 2 100输出4 1 -98说明对于第一组测试数据三种操作得到的答案依次为10 → ⌈ 10 ⌉ 4 10 \to \lceil \sqrt{10} \rceil 410→⌈10​⌉410 → 10 − 1 9 10 \to 10 - 1 910→10−1910 → ⌈ 10 2 ⌉ 5 10 \to \lceil \frac{10}{2} \rceil 510→⌈210​⌉5。综上最小答案为4 44。对于第二组测试数据三种操作得到的答案依次为2 → ⌈ 2 ⌉ 2 2 \to \lceil \sqrt{2} \rceil 22→⌈2​⌉22 → 2 − 1 1 2 \to 2 - 1 12→2−112 → ⌈ 2 2 ⌉ 1 2 \to \lceil \frac{2}{2} \rceil 12→⌈22​⌉1。综上最小答案为1 11。解题思路本题是贪心模拟问题。每次操作可以在“开根号向上取整”“减 1”“除以 2 向上取整”三种中任选一种目标是在m mm次操作后让数字尽可能小。由于减 1 每次固定减少 1而另外两种操作在数字较大时能减少更多但当数字变小后减 1 可能成为最优选择。因此可以在每一步贪心选择当前能使数字最小的操作一旦发现减 1 已经不比另外两种操作差则剩余操作全部使用减 1。1. 问题等价转化三种操作开根号向上取整n → ⌈ n ⌉ n \to \lceil \sqrt{n} \rceiln→⌈n​⌉减 1n → n − 1 n \to n - 1n→n−1除以 2 向上取整n → ⌈ n / 2 ⌉ n \to \lceil n/2 \rceiln→⌈n/2⌉每步选择一种操作执行m mm次求最终可能的最小值。2. 贪心策略在每一步计算两种非线性操作的结果c1 ceil(sqrt(n))c2 ceil(n/2)。取nxt min(c1, c2)。比较n - 1与nxt若n - 1 nxt说明减 1 已经不比另外两种操作差。由于后续继续减 1 每步只减少 1而另外两种操作在后续可能减少更慢甚至不再优于减 1因此剩余所有操作均选择减 1最终结果为n - 剩余操作次数可以直接结束。否则选择nxt作为新的n nn消耗一次操作继续循环。3. 算法步骤读入n , m n, mn,m。只要m 0 m 0m0计算c1 ceil(sqrt(n))即sqrt(n)后若平方不等于原数则加 1。计算c2 (n 1) / 2整数除法向上取整。令best min(c1, c2)。若n - 1 best跳出循环。否则n bestm--。输出n - m跳出循环后剩余的m mm次全部用减 1。4. 复杂度分析时间复杂度每次循环n nn至少减半除以 2或开根号下降速度极快。即使n 10 9 n10^9n109循环次数也不超过约30 3030次。总复杂度O ( T log ⁡ n ) O(T \log n)O(Tlogn)T ≤ 2 × 10 5 T \le 2\times10^5T≤2×105完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结利用减 1 操作的线性特性与另两种操作的快速下降特性在每一步贪心选择最优操作。一旦减 1 不再劣于其他操作则直接采用减 1 填满剩余步数避免不必要的循环。该方法高效且正确。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,m;cinnm;while(m){ll c1sqrt(n);if(c1*c1!n)c1;ll c2(n1)/2;if(n-1min(c1,c2))break;nmin(c1,c2);m--;}coutn-m\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;cint;while(t--)solve();return0;}