「MCOI-06」Flight

题目描述

书虫需要移动他的盾构机。

书虫将 MC 空间抽象为二维平面。他的盾构机现在在 $(a,b)$，而书虫想把盾构机移动到 $(c,d)$。

书虫每一步可以将盾构机向东南西北任何方向行动。但是这盾构机有一个限制：相邻两步不能向同一个方向走！

给定 $(a,b)$ 和 $(c,d)$，请计算书虫最少需要几步将盾构机移动到终点。

求书虫的最少步数。可以证明，他永远可以到达终点。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示表示数据的组数。

接下来 $T$ 行，每行四个整数 $a,b,c,d$，代表一组数据，其中 $(a,b)$ 为起点，$(c,d)$ 为终点。

输出格式

输出 $T$ 行，第 $i$ 行代表第 $i$ 组数据的答案。

样例 #1

样例输入 #1

3
-2 0 -2 1
0 1 3 3
-1 1 1 1

样例输出 #1

1
5
4

提示

样例 1 解释

• 对于第一组，最优策略为 $(-2,0)\to (-2,1)$。
• 对于第二组，最优策略为 $(0,1)\to (1,1)\to (1,2)\to (2,2)\to (2,3)\to (3,3)$。
• 对于第三组，最优策略之一为 $(-1,1)\to (0,1)\to (0,0)\to (1,0)\to (1,1)$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（29 pts）：$0\le a,b,c,d\le 3$。
• Subtask 2（29 pts）：$a=c$。
• Subtask 3（42 pts）：无特殊限制。

对于所有数据，$1\le T\le 10^5$，$|a|,|b|,|c|,|d|\le 10^{18}$。

C++实现

#include
#include
#include
#define int long long
using namespace std;
inline int read() {
int s=0,w=1;
char ch=getchar();
while(ch<‘0’||ch>‘9’) {
if(ch==’-’)w=-1;
ch=getchar();
}
while(ch>=‘0’&&ch<=‘9’)
s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return sw;
}
inline void write(int x) {
if(x>9)
write(x/10);
putchar(x%10+‘0’);
}
signed main() {
int n=read();
while(n–){
int a=read(),b=read();
int c=read(),d=read();
int x=abs(a-c),y=abs(b-d);
if(x>y)swap(x,y);
int ans=0;
ans+=x2;
if(abs(x-y)%2)ans+=abs(x-y)/2*4+1;
else ans+=abs(x-y)*2;
write(ans);
putchar(’\n’);
}
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容