标签搜索

目 录CONTENT

文章目录

字节--踢球问题.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 1,982 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--踢球问题

@[toc]

一、题目描述

有三只球队,每只球队编号分别为球队1,球队2,球队3,这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛,每场比赛不能打平,踢赢一场比赛得一分,输了不得分不减分已知球队1和球队2的比分相差d1分,球队2和球队3的比分相差d2分,每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛,有没有可能三只球队的分数打平

  •  输入描述:
第一行包含一个数字 t (1 <= t <= 10)
接下来的t行每行包括四个数字 n, k, d1, d2
(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)
  •  输出描述:
每行的比分数据,最终三只球队若能够打平,则输出“yes”,
										否则输出“no”

输入例子1:
2
3 3 0 0
3 3 3 3

输出例子1:
yes
no

例子说明1:
case1: 球队1和球队2 差0分,球队2 和球队3也差0分,
					所以可能的赛得分是三只球队各得1分

case2: 球队1和球队2差3分,球队2和球队3差3分,所以可能的
	  得分是 球队1得0分,球队2得3分, 球队3 得0分,比赛
	  已经全部结束因此最终不能打平。

二、分析

  •  因为每场比赛不能打平,踢赢一场比赛得一分,输了不得分不减分,所以这意味着,所有的比赛总分加起来一定是n,打了k场比赛,那么这k长比赛的总分是k;
  •  要注意比赛场数(10^12)非常大,需要使用long long的类型。
  •  解决这道题的关键在于得出三个队伍的具体比分。
  •  我们取一组数据n=150,k=31,d1=15,d2=17。 无论三个队伍的比分最终是怎样的,总是有四种情况
    在这里插入图片描述
  •  下一个问题是怎么知道三个队伍的具体得分,也就是得出unknow的值
  •  这非常简单,由于三个队伍的总分k(即总比赛场数,注意每一局只有人得分没有人扣分)是知道的,因此很容易得出unknow的值,接着判断unknow是不是整数,以及要保证三个队伍的得分为正
    在这里插入图片描述
  •  得出三个队伍的具体分数后,就可以根据剩余场数n-k进行判断

例如剩余场数150 - 31 = 119 119 - (22 - 7) - (22 - 5) = 87
由于87是三的倍数,这剩下的87场比赛可以让3个队伍平均分得分。
因此是有可能平均的。

三、代码

#include<iostream>
using namespace std;

//n代表总场数
//k代表已经进行的场数
//t1代表队伍1的分数
//...
//...
bool check(long long n,long long k,long long t1,long long t2,long long t3)
{
	//如果已经进行了k场所获的的k分,反而不能被3整除,直接返回false
	//就是4种情况中的前两种情况
	if((k - t1 - t2 - t3) % 3 != 0)
	{
		return false;
	}
	else
	{
		//相当于求得表中的unknow
		long long temp = (k - t1 - t2 - t3) / 3;
		//求得每个队伍经过k场后的真实得分的
		t1 += temp;
		t2 += temp;
		t3 += temp;

		//如果出现某个队伍的分数为负,直接返回
		if(t1 < 0 || t2 < 0 || t3 < 0)
		{
			return false;
		}
		else
		{
			//获取3个队伍当中最大的分数
			long long max;
			max = t1 > t2 ? t1 : t2;
			max = max > t3 ? max : t3;
			
			//求把剩下两个分数较小的队伍补齐到和最大分数的队伍所需的分数
			long long need_remain = 3 * max - t1 - t2 - t3;

			//n场还剩下的场数,也就是待均分的分数
			long long remain = n - k;

			//判断剩余场数能不能打赢,如果剩下的分数能被3个队伍均分直接返回true,反之返回false 
			if(need_remain <= remain && (remain - need_remain) % 3 == 0) 
				return true;
			else
			{
				return false;
			}
			
		}
	}
}

int main()
{
	long long t;
	cin >> t;
	long long n,k,d1,d2;
	while(t--)
	{
		cin >> n >> k >> d1 >> d2;
		//判断四种情况下每种平局的可能性,只要有一种可能性成立即可 
		if(check(n,k,d1,0,d2) || check(n,k,d1,0,-d2)||check(n,k,-d1,0,d2)||check(n,k,-d1,0,-d2))
			cout << "yes"<<endl;
		else 
			cout << "no"<<endl;
	}
	return 0;
} 
0

评论区