codeforce每日一题链接
题目链接
题目分数:1700
这道题跟力扣的每日一题很像 LCP 33. 蓄水
题目描述
给你一个点$(n, m)$,开始的步长$k$是1,你的初始位置是$(0, 0)$,你有三种操作,一种是让$k$加$1$,一种是让横坐标加$k$,另一种是让纵坐标加$k$。请问最少要多少次操作走到$(n, m)$。
样例
输入样例1
3
1 1
1 6
8 4
输出样例1
2
5
6
算法
(枚举) $O(n)$
横坐标和纵坐标的跳跃是独立的。假设最终的步长是$k$,那么对步长的操作有$k-1$次,那么对于横坐标,当步长是$k$时,跳跃次数为$n/k$次,但是如果无法整除,说明之前在步长从$1$加到$k$的过程中跳跃了一次,所以可以合并写为$n/k$上取整;同理,纵坐标也是。所以我们可以暴力枚举步长,维护一个最小值。
c++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n>>m;
LL res = 1e9;
for(int i=1;i<=1e5;i++)
res = min(res, (LL)i - 1 + (n + i - 1) / i + (m + i - 1) / i);
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
Python 代码
# https://www.acwing.com/blog/content/34755/
for i in range(int(input())):
a, b = map(int, input().split())
ans = a + b
for m in range(1, 100000):
ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1))
print(ans)
可以滴
🥰