算法题每日一练---第29天：角逐冠军-阿里云开发者社区

算法题每日一练---第29天：角逐冠军

2022-04-12 267

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。

一、问题描述

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。

球赛的规则如下：

如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。

根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

二、题目要求

考察

数学思想，规律
STL的set标准模板库
建议用时：10~25min

三、问题分析

看了上面的球赛规则是不是感到无从下手，什么叫谁打败了谁，谁又一定打败谁？

我们反着思考，既然一场比赛有胜有负，那么决出冠军的比赛肯定是一个人没输过，那他不就赢了。

把胜利的人放在一起，失败的人放在一起。只要胜利的人数比失败的人数多1个，那么就能决出冠军。可以用C++的set存储人数，防止重复

四、编码实现

#include<iostream>#include<set>//头文件usingnamespacestd;
intmain()
{
set<char>s1,s2;//定义字符型chara,b;
inti,n;
cin>>n;//输入for(i=0;i<n;i++)//循环输入比赛结果，第一个获胜    {
cin>>a>>b;
s1.insert(a);//胜利的人存入s2.insert(b);//失败的人存入    }
if(s1.size()-s2.size()==1)//胜利的人数比失败多一个    {
cout<<"Y";//胜者    }
elsecout<<"N";//无return0;
}