首页 > 编程学习 > 2021 XJCPC—G. cocktail with snake

2021 XJCPC—G. cocktail with snake

发布时间:2022/1/17 12:21:03

在这里插入图片描述
在这里插入图片描述
大致题意:在n * m的点阵里,点A从(1, 1)出发,沿题意所示的方向进行弓形走位(就是遇到边界就会向上拐弯),问走到第k步时的曼哈顿距离

分析:这类题的难点是判断当前的位置是往右边界去还是从右边界回来(分奇偶)

注意到向上这一段距离也可等效于(看成)水平方向上从x = 0 ~ x = 1 这一段因此,当再次回到 x = 1直线上时为一个周期,此时恰好水平方向上一个来回,走了两个拐弯,此时d = 2 * n

所以通过判断 k % n的值进行分类讨论即可,而k / n 表示走了多少个半个周期, 而且表示竖直方向上走过的距离,k % n贡献水平方向上的距离,在回来时贡献为- k % n
即可解决

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int t;
    cin >> t;

    while (t --)
    {
        int ans = 0;
        int n , m , k;
        cin >> n >> m >> k;

        if (((k / n) % 2) == 0)
        {
            ans += (k / n) + (k % n);
        }

        else
        {
            ans += (k / n) + (n - k % n - 1);
        }

        cout << ans << endl;
    }
    
    return 0;
}
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000