刷题与ZZ错误记录14

HDU-1052 Tian Ji -- The Horse Racing

题面

【VJudge】 【HDU】

就是一个实现设计田忌式赛马策略的程序

总结

因为题目里有这么一句话,让我迷惑了好一会儿:

In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

在这种情况下,加权二分匹配算法是解决该问题的过于先进的工具。

加权二分匹配?

实际上题目十分明显地告诉了你这其实是田忌赛马题(这标题不就是田忌赛马吗?我还饶有兴致地看完了英文版的背景描述)。我们只需要按照田忌的策略完成这道题就可以了。

简单来说,就是(按照顺序进行比较,满足了就结束比较,否则继续看下一条):

  1. 如果田忌最慢的马跑得比大王 最慢的马,那么田忌就使用这匹马跟大王最慢的马比赛(最慢的马都能跑过又怎么能为了一匹最慢的马浪费了一匹快马呢?);
  2. 如果田忌最慢的马跑得比大王 最慢的马,那么田忌就要勇敢些,将这匹最慢的马拿去和大王最快的马比赛(反正这匹马怎么弄都是输还不如让他去消耗掉大王最快的马)!
  3. 如果田忌 最快的马跑得比大王 最快的马要,那么田忌需要用这匹马去跟大王最快的马比赛,获得胜利的机会(别的马又不一定行,拿这匹马跟慢马比赛就是浪费)!
  4. 如果田忌 最快的马跑得比大王 最快的马要,田忌需要用最慢的那匹马与大王最快的马比赛,浪费掉大王的快马,为自己争取胜利的机会!
  5. 如果田忌 最快的马跑得比大王 最快的马一样快,那么就拿最慢的那匹马去和王最快的马比赛,平局的代价跟后面输一局后大王的快马没有田忌的快马快,赢过来差不多。

AC代码

#include<bits/stdc++.h>
using namespace std;
int tmp,n,ans;
deque<int> tian,king;
int main (){
    while(1){
        scanf("%d",&n);
        if(n==0)return 0;
        tian.clear();king.clear();ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&tmp);
            tian.push_back(tmp);
        }sort(tian.begin(),tian.end(),greater<int>());
        for(int i=1;i<=n;i++){
            scanf("%d",&tmp);
            king.push_back(tmp);
        }sort(king.begin(),king.end(),greater<int>());
        while(n){
            if(tian.back()>king.back()){
                ans++;tian.pop_back();
                king.pop_back();n--;
            }else if(tian.back()<king.back()){
                ans--;tian.pop_back();
                king.pop_front();n--;
            }else if(tian.front()>king.front()){
                ans++;tian.pop_front();
                king.pop_front();n--;
            }else if(tian.front()<king.front()){
                ans--;tian.pop_back();
                king.pop_front();n--;
            }else if(tian.back()>king.front()){
                ans++;tian.pop_back();
                king.pop_front();n--;
            }else if(tian.back()<king.front()){
                ans--;tian.pop_back();
                king.pop_front();n--;
            }else{
                tian.pop_back();
                king.pop_front();n--;
            }
        }
        printf("%d\n",ans*200);
    }
}

页面: 1 2 3 4 5 6 7

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注