网硕互联帮助中心小数字
时间限制：1 秒 空间限制：256 MB 知识点：模拟
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
小娴给阿笙出了一种简单数学题，小娴给出数字
n
n
n，并规定三种操作：
- 若
n
n
n 为非负整数，开根号（向上取整），即n
→
⌈
n
⌉
n \\to \\lceil \\sqrt{n} \\rceil
n→⌈n⌉； - 对当前的数字
n
n
n 减1
1
1，即n
→
n
−
1
n \\to n – 1
n→n−1； - 对当前数字除以
2
2
2（向上取整），即n
→
⌈
n
2
⌉
n \\to \\lceil \\frac{n}{2} \\rceil
n→⌈2n⌉。
现在可以对数字
n
n
n 操作
m
m
m 次，小娴想让阿笙计算出操作
m
m
m 次之后
n
n
n 最小可以为多少。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
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
m
m 次之后
n
n
n 最小可以为多少。
示例 1
输入：
3
10 1
2 1
2 100
输出：
4
1
-98
说明： 对于第一组测试数据，三种操作得到的答案依次为：
10
→
⌈
10
⌉
=
4
10 \\to \\lceil \\sqrt{10} \\rceil = 4
10→⌈10
⌉=4；
10
→
10
−
1
=
9
10 \\to 10 – 1 = 9
10→10−1=9；
10
→
⌈
10
2
⌉
=
5
10 \\to \\lceil \\frac{10}{2} \\rceil = 5
10→⌈210⌉=5。综上，最小答案为
4
4
4。
对于第二组测试数据，三种操作得到的答案依次为：
2
→
⌈
2
⌉
=
2
2 \\to \\lceil \\sqrt{2} \\rceil = 2
2→⌈2
⌉=2；
2
→
2
−
1
=
1
2 \\to 2 – 1 = 1
2→2−1=1；
2
→
⌈
2
2
⌉
=
1
2 \\to \\lceil \\frac{2}{2} \\rceil = 1
2→⌈22⌉=1。综上，最小答案为
1
1
1。
解题思路
本题是贪心模拟问题。每次操作可以在“开根号向上取整”“减 1”“除以 2 向上取整”三种中任选一种，目标是在
m
m
m 次操作后让数字尽可能小。由于减 1 每次固定减少 1，而另外两种操作在数字较大时能减少更多，但当数字变小后，减 1 可能成为最优选择。因此可以在每一步贪心选择当前能使数字最小的操作，一旦发现减 1 已经不比另外两种操作差，则剩余操作全部使用减 1。
1. 问题等价转化
- 三种操作：
- 开根号向上取整：
n
→
⌈
n
⌉
n \\to \\lceil \\sqrt{n} \\rceil
n→⌈n⌉ - 减 1：
n
→
n
−
1
n \\to n – 1
n→n−1 - 除以 2 向上取整：
n
→
⌈
n
/
2
⌉
n \\to \\lceil n/2 \\rceil
n→⌈n/2⌉
- 开根号向上取整：
- 每步选择一种操作，执行
m
m
m 次，求最终可能的最小值。
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
n
n，消耗一次操作，继续循环。
3. 算法步骤
n
,
m
n, m
n,m。
m
>
0
m > 0
m>0：
- 计算 c1 = ceil(sqrt(n))，即 sqrt(n) 后若平方不等于原数则加 1。
- 计算 c2 = (n + 1) / 2（整数除法向上取整）。
- 令 best = min(c1, c2)。
- 若 n – 1 <= best，跳出循环。
- 否则 n = best，m–。
m
m
m 次全部用减 1）。
4. 复杂度分析
- 时间复杂度：每次循环
n
n
n 至少减半（除以 2）或开根号，下降速度极快。即使n
=
10
9
n=10^9
n=109，循环次数也不超过约30
30
30 次。总复杂度O
(
T
log
n
)
O(T \\log n)
O(Tlogn)，T
≤
2
×
10
5
T \\le 2\\times10^5
T≤2×105，完全可行。 - 空间复杂度：
O
(
1
)
O(1)
O(1)，仅使用几个变量。
总结
利用减 1 操作的线性特性与另两种操作的快速下降特性，在每一步贪心选择最优操作。一旦减 1 不再劣于其他操作，则直接采用减 1 填满剩余步数，避免不必要的循环。该方法高效且正确。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
void solve()
{
ll n,m;
cin>>n>>m;
while(m)
{
ll c1=sqrt(n);
if(c1*c1!=n) c1++;
ll c2=(n+1)/2;
if(n–1<=min(c1,c2)) break;
n=min(c1,c2);
m—;
}
cout<<n–m<<'\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll t=1;
cin>>t;
while(t—) solve();
return 0;
}
评论前必须登录！
注册