专栏文章

题解：CF1814B Long Legs

ssongge888
CF1814B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9ag9t
此快照首次捕获于
2025/12/03 08:15
3 个月前
此快照最后确认于
2025/12/03 08:15
3 个月前
查看原文

CF1814B Long Legs

题意

给定起点 (0,0)(0,0)，终点 (x,y)(x,y)，初始步长为 11，你可以执行以下三种操作：
  1. 移动到 (x+m,y)(x+m, y)。
  2. 移动到 (x,y+m)(x, y+m)。
  3. 步长 m→m+1m \rightarrow m+1。
求从 (0,0)(0,0) 到 (x,y)(x,y) 的最少操作次数。

思路

假设最终步长为 mm，则需要的操作次数为：
f(m)=⌈xm⌉+⌈ym⌉+(m−1)(1)f(m) = \left\lceil \frac{x}{m} \right\rceil + \left\lceil \frac{y}{m} \right\rceil +(m-1) \tag 1
此时 f(m)f(m) 是离散的，不好分析，不妨把上取整先去掉，即：
f(m)=x+ym+m−1(2)f(m)= \frac{x+y}{m} +m-1 \tag 2
目的是求 f(m)f(m) 的最小值。
可以推出来 f′(m)f^′(m) 如下：
f′(m)=−x+ym2+1(3)f^′(m)= - \frac{x+y}{m^2}+1 \tag 3
在 m=x+ym=\sqrt{x+y} 的时候，(1)(1) 式近似可以取到最小值，但是可能会出现误差，可以把 mm 附近的数都枚举一下取最优情况就可以了。

Code

CPP
#include<bits/stdc++.h>
#define int long long
#define double long double
#define bug cout<<"___songge888___"<<'\n';
using namespace std;
int t,a,b;
int ans;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>a>>b;
        int m=sqrt(a+b);
        ans=1e18;
        for(int i=max(m-100,1ll);i<=m+100;i++){
            ans=min(ans,(int)(ceil(a*1.0/i))+(int)(ceil(b*1.0/i))+i-1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
提交记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...