AcWing 1237. 10行代码优雅解决螺旋折线所有情况

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1237. 10行代码优雅解决螺旋折线所有情况原题链接中等

作者：

baitianshuijiao , 2021-03-16 09:17:37 , 所有人可见 , 阅读 3742

157

26

-
不知为何点赞越来越多，来更新一下这个题的详细思路。 - 2022/3/18
-
找规律可以发现每层的右上角点所需步数为为 $4k^2$ ，求任意一个点的dis首先找到这个点所在的层数

如果在该层的左或上则减去该点到右上角曼哈顿距离，
如果在该层的右或下则加上该点到右上角曼哈顿距离；

不懂曼哈顿距离的可以先百度一下，十分简单的定义，思路不懂的可以在评论区留言或看下评论区的解释。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long x,y; cin>>x>>y;
    long long k = max(abs(x), abs(y));
    if(x >= y) cout<<4 * k * k + abs(x - k) + abs(y - k)<<endl;
    else cout<<4 * k * k - abs(x - k) - abs(y - k)<<endl;
    return 0;
}

45 评论

正态 2024-01-15 16:59

曼哈顿距离就是，两点间只走平行于坐标轴直线的距离之和。
比如直角坐标系中，就是只走平行线、垂直线，相加就是曼哈顿距离，对应题目中的折线构成。

正态 2024-01-15 17:40

贴个自己理解滴注释

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()
{
    LL x, y;
    cin >> x >> y;
    //1.寻找点所在的层数
    //-------
    LL k = max(abs(x) , abs(y) );   //注意先取绝对值，然后取max，若是负数取max之后，绝对值是小的，对应层数就错误了
    //-------
    //找规律发现 y = x对角线的步数恰好是 4 * x^2 （x 和 y相等，此处写哪个都可以）
    //2.根据在中间节点的前后，判断前进还是后退。（以y=x直线作为划分）
    LL res = 0;
    if(x >= y) //对角线的下半部分，加上距离对角点的曼哈顿距离
        res = 4 * k * k + abs(k - x) + abs(k - y); //前进
    else   
        res = 4 * k * k - abs(k - x) - abs(k - y); //后退

    cout << res << endl;
    return 0;
}