我要招人

去企业版

首页 > 试题广场 >

走斜线

[编程题]走斜线

热度指数：470 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有天他来到一张方格地图上，整张地图可以看做一个二维坐标轴。牛牛此刻处于原点（0,0），他想要到点（x,y）去。

牛牛有强迫症，他规定自己必须恰好k步走到点(x,y)，中途可以经过任何点包括（x,y），但是第k步一定要到达（x,y）。

一步有八种走法，直线东（+1,0）南（0,-1）西（-1,0）北（0,+1），斜线东南（+1,-1）东北（+1,+1）西南（-1,-1）西北（-1,+1）。

牛牛会在能k步到达目的地的基础下尽量走斜线，你能计算出牛牛到底走了多少条斜线吗？

输入描述:

第一行一个整数T，代表数据组数。
每组数据给出三个整数x，y，k。

输出描述:

对于每组数据，单独一行输出一个整数。
如果牛牛可以在第k步的时候到达(x,y)，输出牛牛走的斜线数量。
如果牛牛不能到达，输出-1。

示例1

输入

2
2 3 4
7 7 9

输出

3
9

示例2

输入

1
1 2 1

输出

-1

备注:

对于100%的数据，1<=T<=1000，1<=x，y，k<=1000000000000000000。

算法知识视频讲解

kyzheng

# Python版本，通过所有算例，供参考
def judge(x, y, k):
    x = abs(x)
    y = abs(y)

    if k < max(x, y):
        return -1
    elif k == max(x, y):
        if (x+y) % 2 == 0:
            return k
        elif (x+y) % 2 == 1:
            return k-1
    elif k > max(x, y):
        if (k - max(x, y)) % 2 == 0:
            if (x + y) % 2 == 0:
                return k
            elif (x + y) % 2 == 1:
                return k - 1
        elif (k - max(x, y)) % 2 == 1:
            if (x + y) % 2 == 0:
                return k - 2
            elif (x + y) % 2 == 1:
                return k - 1

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    a[i] = input().split()

for i in range(n):
    for j in range(len(a[i])):
        a[i][j] = int(a[i][j])

for i in range(n):
    x = a[i][0]
    y = a[i][1]
    k = a[i][2]

    res = judge(x, y, k)

    print(res)

发表于 2022-03-11 23:08:17 回复(0)

清霜

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                long x = scanner.nextLong();
                long y = scanner.nextLong();
                long k = scanner.nextLong();
                long sum = x + y;
                long a = Math.max(x,y);
                if(a > k){
                    System.out.println(-1);
                    continue;
                }
                if(sum % 2 != 0){
                    System.out.println(k-1);
                }else{
                    long y1 = (k-a)%2;
                    if(y1!=0){
                        System.out.println(k-2);
                    }else{
                        System.out.println(k);
                    }
                }
            }
        }
    }
}

发表于 2020-04-19 19:31:17 回复(0)

黄色变白色

#include<iostream>
#include<cmath>

using namespace std;

void countUnequal(long long int x,long long int y,long long int n) //x为目标点的最大值，y为小值
{
    if((n-x) < 0) //步数太少，走不到目标点
    {
        cout << "-1"<<endl;
        //这里一定要加返回值，留下了心酸的泪水，检查了好久逻辑问题，最后是这里的锅
        return;
    }

if((x-y)%2 == 0) //走完(y,y)的正方形后还剩的步数为偶数
{
    if((n -y)%2)
        {
            cout << n - 2 << endl;
        }
        else
        {
            cout << n << endl;
        }
    }
    else if((x-y)%2)//走完(y,y)的正方形后还剩的步数为奇数
    {
cout << n -1 << endl;
    }
}

void countMax(long long int x,long long int y,long long int n)
{
if(x == y) //如果目标点的横轴等于纵轴,且不在原点
{
         if(n < y)
        {
            cout << "-1"<<endl;;
        }
        else if((n - y)%2 == 1)
        {
            cout <<n - 2<<endl;;
        }
        else
        {
            cout << n<<endl;
        }
}
else if(x > y)
countUnequal(x,y,n);
else if(x < y)
countUnequal(y,x,n);
}

int main()
{
    int t;
    long long int x,y,n;
    cin >> t;
    for(int i = 0;i < t;i++)
    {
        cin >> x>> y >> n;
        countMax(x,y,n);
    }

    return 0;
}

发表于 2019-07-18 12:09:53 回复(0)

N_I

#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    while(n){
        long long int x, y, k;
        cin >> x >> y >> k;
        
        long long int max =  x < y?y:x;
        long long int min =  x > y?y:x;
        
        if (k < max){
        	cout << "-1" << endl;
		}else{
            long long int t = min + (max-min)/2*2;
            if((max-min)%2 == 0){
            	if((k - t)%2 == 0){
            		cout << k << endl;
				}else{
					cout << k - 2 << endl;
				}
			}else{
            	cout << k-1 << endl;
			}
        }
        n--;
    }
    return 0; 
}

一直没发通过测试，看了其他人的答案才发现int小了，存不下

发表于 2020-05-20 22:39:28 回复(0)

xxLilyxxZ

#include <iostream>
using namespace std;
long long max(long long x, long long y){
	return x>y?x:y;
}
void getStep(long long x, long long y, long long k){
	long long minstep,remins;
    long long sum=x+y;
	if(sum%2==0){
		minstep=max(x,y);
		if(k<minstep)
			cout<<-1<<endl;
		else{
			remins=k-minstep;
			if(remins%2==0)
                cout<<k<<endl;     				
			else          
                cout<<k-2<<endl;       
		}
	}else{
		if(x>y)
			minstep=x-1;
		else
			minstep=y-1;
		if(k<minstep+1)
			cout<<-1<<endl;
		else
			cout<<k-1<<endl;
	}
	return;
}
int main(){
	long long t,x,y,k;
	cin>>t;
	while(t-->0){
		cin>>x>>y>>k;
		getStep(x,y,k);
	}
	return 0;
}

发表于 2020-02-20 21:26:48 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师数据库工程师信息技术岗贪心区块链模拟测试开发工程师 2019 数学大数据开发工程师数据分析师 Java工程师牛客

来自：2019校招-留学生招...

上传者：小小

难度：

5条回答 15收藏 5198浏览

通过挑战的用户

小鬼鑫鑫

2023-01-15 01:15:32
靠谱的大魔王在喝茶

2022-09-22 02:05:23
享尔

2022-09-06 22:51:25
牛客90518...

2022-07-22 17:47:07
hzkk

2022-07-14 22:19:57

走斜线

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题