AcWing 1219. 移动距离
原题链接
简单
作者:
目目目
,
2022-04-27 12:07:45
,
所有人可见
,
阅读 2864
0 1 2 3 4 5 0 1 2 3 4 5
11 10 9 8 7 6 6 7 8 9 10 11
12 13 14 15 16 17 12 13 14 15 16 17
23 22 21 20 19 18 18 19 20 21 22 23
即将8置换成10
算法1:
#include<iostream>
using namespace std;
const int N = 100100;
int a[N], w, m, n;
pair<int, int> x, y;
int main()
{
int cnt = 1;
cin >> w >> m >> n;
for (int i = 0; i <= N; i++)
{
if (i % 2)
for (int j = w * (i + 1); j >= i * w + 1; j--)
{
if (j == m) x = { i,cnt - i * w };
if (j == n) y = { i,cnt - i * w };
a[cnt++] = j;
}
else
for (int j = i * w + 1; j <= w * (i + 1); j++)
{
if (j == m) x = { i,cnt - i * w };
if (j == n) y = { i,cnt - i * w };
a[cnt++] = j;
}
if (cnt >= m && cnt >= n) break;
}
cout << abs(x.first - y.first) + abs(x.second - y.second);
}
算法2:
#include<iostream>
using namespace std;
const int N = 10010;
int w, n, m;
int reverse(int x)
{
int start = w * (x / w), end = start + w - 1;
return start + (end - x);
}
int get(int x)
{
//如果该行是偶数行,即该行是递减排列的,则将该数置换
if ((x / w) % 2) return reverse(x);
return x;
}
int main()
{
cin >> w >> m >> n;
m--, n--; //序号减1,使每行的所有元素/w后的值相同
m = get(m), n = get(n);
cout << abs(m / w - n / w) + abs(m % w - n % w);
}
你算法1的 cnt 最开始赋值为 0 比较好,现在最后一个样例过不去了