CF 1036 B Diagonal Walking v.2 —— 思路

题目:http://codeforces.com/contest/1036/problem/B

题意:从 (0,0) 走到 (n,m),每一步可以向八个方向走一格,问恰好走 k 步能否到达,能到达则输出最多能走多少斜步;

自己想得太复杂了...

首先,判断 -1 就看横纵距离中的较大值是否大于 k ,因为最少走 max(n,m) 步可以到达;

设 m > n;

如果 m - n 为奇数,那么显然会有一步必须直着走,那么 k --;

这里可以通过走法来调节剩余步数的奇偶,就是直着走过去或者拐一下走过去的区别,所以到达后不会再有 k 的损失;

如果 m - n 为偶数,首先可以全部斜着走过去;

到达以后的剩余步数如果是偶数,那么来回进出终点,不会有斜着走的损失;

如果是奇数,则会损失两步,会有两个直着走的步来代替一个斜着走;

这题就做完了-_-

原文地址:https://www.cnblogs.com/Zinn/p/9607987.html