华为机试题：渊子赛马

迈不过友情╰ 2022-08-20 07:24 93阅读 0赞

<table style="margin:0px; padding:0px; width:970px; border:0px; border-collapse:collapse; border-spacing:0px; empty-cells:show; color:rgb(0,0,0); font-family:'Times New Roman',Arial,微软雅黑,宋体,Tahoma,Helvetica,SimSun,sans-serif,宋体"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px; height:26px"> 
   <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 描述:&nbsp;</td> 
   <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <h2 style="margin:0px; padding:0px">题目描述</h2> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。&nbsp;赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。”&nbsp;孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。&nbsp;比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。&nbsp;就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有N(1≤N≤1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。</p> <h2 style="margin:0px; padding:0px">输入</h2> 
    <div style="margin:0px; padding:0px"> 
     <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 输入有多组测试数据。&nbsp;每组测试数据包括3行：&nbsp;第一行输入N(1≤N≤1000)。表示马的数量。&nbsp;第二行有N个整型数字，即渊子的N匹马的速度。&nbsp;第三行有N个整型数字，即对手的N匹马的速度。&nbsp;当N为0时退出。</p> 
    </div> <h2 style="margin:0px; padding:0px">输出</h2> 
    <div style="margin:0px; padding:0px"> 
     <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出“YES”。&nbsp;否则输出“NO”。</p> 
    </div> <h2 style="margin:0px; padding:0px">样例输入</h2> 
    <div style="margin:0px; padding:0px"> 
     <span style="margin:0px; padding:0px"></span> 
     <pre style="margin-top:0px; margin-bottom:0px; padding:0px; white-space:pre-wrap; word-wrap:break-word; line-height:24px">5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0</pre> 
    </div> <h2 style="margin:0px; padding:0px">样例输出</h2> 
    <div style="margin:0px; padding:0px"> 
     <span style="margin:0px; padding:0px"></span> 
     <pre style="margin-top:0px; margin-bottom:0px; padding:0px; white-space:pre-wrap; word-wrap:break-word; line-height:24px">YES
NO</pre> 
     <pre style="margin-top:0px; margin-bottom:0px; padding:0px; white-space:pre-wrap; word-wrap:break-word; line-height:24px"></pre> 
    </div> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="margin:0px; padding:0px"><span style="margin:0px; padding:0px; font-size:24px">接口说明</span></span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 原型：char&nbsp;*&nbsp;IsYuanziWin(unsigned&nbsp;int&nbsp;num,&nbsp;unsigned&nbsp;int&nbsp;*&nbsp;speed_yz,&nbsp;unsigned&nbsp;int&nbsp;*&nbsp;speed_op)</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 功能:判断yuanzi&nbsp;的马是否会赢？yuanzi&nbsp;的马赢了，返回&nbsp;YES.&nbsp;否则返回&nbsp;NO<br style="margin:0px; padding:0px"> &nbsp;&nbsp;&nbsp;&nbsp;<br style="margin:0px; padding:0px"> 输入参数：<br style="margin:0px; padding:0px"> unsigned&nbsp;int&nbsp;num:&nbsp;赛马的数量；&nbsp;&nbsp;&nbsp;(1&lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> &lt;=&nbsp;num&nbsp;&lt;=1000)<br style="margin:0px; padding:0px"> unsigned&nbsp;int&nbsp;*&nbsp;speed_yz:&nbsp;yuanzi&nbsp;的马的速度；<br style="margin:0px; padding:0px"> unsigned&nbsp;int&nbsp;*&nbsp;speed_op:&nbsp;对手的马的速度；<br style="margin:0px; padding:0px"> 输出参数：<br style="margin:0px; padding:0px"> &nbsp;&nbsp;&nbsp;无&nbsp;&nbsp;<br style="margin:0px; padding:0px"> 返回值：<br style="margin:0px; padding:0px"> &nbsp;&nbsp;char&nbsp;*&nbsp;型&nbsp;的字符串，yuanzi&nbsp;的马赢了，返回&nbsp;YES.&nbsp;否则返回&nbsp;NO；</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> &nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

#include <algorithm>
    #include <stdlib.h>
    #include "OJ.h"
     
    using namespace std;
    /*
    功能:判断yuanzi 的马是否会赢？yuanzi 的马赢了，返回 YES. 否则返回 NO
        
    输入参数：
    unsigned int num: 赛马的数量；   (1<= num <=1000)
    unsigned int * speed_yz: yuanzi 的马的速度；
    unsigned int * speed_op: 对手的马的速度；
    输出参数：
    	 	无 	
    返回值：
    		char * 型 的字符串，yuanzi 的马赢了，返回 YES. 否则返回 NO；
    
    */
    
    char * IsYuanziWin(unsigned int num, unsigned int * speed_yz, unsigned int * speed_op)
    {
    	/*对输入的数据进行排序*/
    	sort(speed_yz, speed_yz + num);
    	sort(speed_op, speed_op + num);
    
    	int i = 0, j = 0,count = 0, start = 0;
    
    	for (int i = 0; i < num; i++)
    	{
    		for (j = start; j < num; j++)
    		{
    			if (speed_yz[i] > speed_op[j])
    			{
    				count++;
    				start = j + 1;
    				break;
    			}
    		}
    	}
    
    	if (count > num / 2)
    	{
    		return "YES";
    	}
    
    	return "NO";
    }