文章	评论	标签
14	12	12

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

?原题复现

背景

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

输入格式

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

输出格式

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

输入样例

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

输出样例

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

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;
}

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

Nickwald