【题解】老王赛马/渊子赛马

[tip type='info']北邮C++实验题4-1,抄作业请直接翻最底下[/tip]

?原题复现

背景

赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到达齐国国都。
赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王,下到大臣,常常以赛马取乐,并以重金赌输赢。田忌多次与国王及其他大臣赌输赢,屡赌屡输。一天他赛马又输了,回家后闷闷不乐。孙膑安慰他说:“下次有机会带我到马场看看,也许我能帮你。”
孙膑仔细观察后发现,田忌的马和其他人的马相差并不远,只是策略运用不当,以致失败。
比赛前田忌按照孙膑的主意,用上等马鞍将下等马装饰起来,冒充上等马,与齐王的上等马比赛。第二场比赛,还是按照孙膑的安排,田忌用自己的上等马与国王的中等马比赛,在一片喝彩中,只见田忌的马竟然冲到齐王的马前面,赢了第二场。关键的第三场,田忌的中等马和国王的下等马比赛,田忌的马又一次冲到国王的马前面,结果二比一,田忌赢了国王。
就是这么简单,现在老王也来赛一赛马。假设每匹马都有恒定的速度,所以速度大的马一定比速度小的马先到终点(没有意外!!)。不允许出现平局。最后谁赢的场数多于一半(不包括一半),谁就是赢家(可能没有赢家)。老王有$N$匹马参加比赛。对手的马的数量与老王马的数量一样,并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果,看看老王能否赢得比赛。

输入格式

输入有多组测试数据。
每组测试数据包括3行:
第一行输入$N$($1\le N\le 1000$)。表示马的数量。
第二行有$N$个整型数字,即老王的N匹马的速度。
第三行有$N$个整型数字,即对手的N匹马的速度。
当$N$为$0$时退出。

输出格式

若通过聪明的你精心安排,如果老王能赢得比赛,那么输出“$YES$”。
否则输出“$NO$”。

输入样例

在这里给出一组输入。例如:

5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0

输出样例

在这里给出相应的输出。例如:

YES
NO

限制

代码长度限制:16 KB
时间限制:400 ms
内存限制:64 MB


?分析

让我们先回到这道题的背景,田忌赛马是如何让自己胜利的呢?
孙膑建议让上等马对中等马,中等马对下等马,虽然下等马对上等马吃了亏,但是仍然以3比2获得了胜利。
个中玄妙,在乎 资源利用最大化

赛马算法v1.0(贪心)

我们发现,要想获得全局最优解,可以从局部最优解出发。要想获胜概率$max$,需要的是手头每匹马都被最充分的利用。
何谓最充分的利用呢?答案就是每匹马都 险胜
先考虑上等马,上等马可以对中等马和下等马。如果对下等马,那么上等马多出来的优势就被浪费了,所以,上等马应该对中等马。
现在,我们可以用自然语言描述我们的赛马算法v1.0了:

  • 从我方上等马开始,匹配对方 次一级马
  • 循环,并记录赢数
  • 最后判断是否获胜

赛马算法v2.0(优化)

我们能不能更近一步呢?
题目并没有说需要给出具体的比赛策略,即谁和谁比并不需要我们考虑。那么,我们是否能整体考虑,直接判断可能性呢?
题目说,只要胜利数超过$\frac{N}{2}$即可判断老王赢,我们可以直接将问题缩小规模,等价为 一半的马 是否能赢。
为此,我们可以直接从对方中等马开始,直接用自己的上等马比赛。只要其中任何一局输了,胜利数就不可能超过$\frac{N}{2}$,自然不可能获胜。

时间复杂度可以直接打折的说。

最后给出代码实现。

?代码实现

赛马算法v1.0

//赛马算法v1.0
#include <iostream>
#include <algorithm>

using namespace std;
int Win(int speed_Y[],int speed_E[],int N){
    int n=0,index=0;
    for(int i=0;i<N;i++)
        if(speed_Y[i]<=speed_E[index]) continue;
        else {
            n++;
            index=index+1;
            continue;
        }
    return n;
}
int main(void){
    int N=1,n,k;
    int speed_Y[1001]={0};
    int speed_E[1001]={0};
    cin>>N;
    while(N){
        for(int i=0;i<N;i++)cin>>speed_Y[i];
        sort(speed_Y,speed_Y+N);
        for(int i=0;i<N;i++)cin>>speed_E[i];
        sort(speed_E,speed_E+N);
        n=Win(speed_Y,speed_E,N);
        cin>>k;
        if(n>N/2+1)
            if(k)cout<<"YES"<<endl;
            else cout<<"YES";
        else
            if(k)cout<<"NO"<<endl;
            else cout<<"NO";
        N=k;
    }
}

赛马算法v2.0

//赛马算法v2.0
#include<algorithm>
#include<iostream>
using namespace std;
int f(int a[],int b[],int n)
{
        sort(a,a+n);
        sort(b,b+n);
        for(int i=n-1,j=n/2;i>=(n-1)/2;i--,j--)
            if(a[i]<=b[j])
            return 0;
        return 1;
}
int main()
{
    int nq=0;
    cin>>n;
    do{
        int a[n],b[n]; 
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++)cin>>b[i];
        q=f(a,b,n);
        cin>>n;
        if(q)
            if(n)cout<<"YES"<<endl;
            else cout<<"YES";
        else
            if(n)cout<<"NO"<<endl;
            else cout<<"NO";
    }while(n);
    return 0;
}
评论区
头像
文章目录