Blog·Tanky WooABOUTRSS

HDOJ 1052 Tian Ji -- The Horse Racing

22 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

此题贪心策略也~~~

怎么贪?赢少输多!

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1052

思路:

----------------------------------------------------------- 贪心策略: 先把田忌和国王的马按从慢到快排序 1.田忌最慢的马比国王最慢的马快    则直接比赛 2.田忌最慢的马比国王最慢的马慢    则田忌最慢的马与国王最快的马比(想想为何?) 3.田忌最慢的马与国王最慢的马一样快    则再比较田忌最快的马比国王最快的马:       同样,①:田忌最快的比国王最快的快:                  比赛    ②:田忌最快的比国王最快的慢:            田忌最慢的与国王最快的比    ③:田忌最快的和国王最快的一样快:这里又要考虑           一:若田忌最慢的和最快的一样,        如:20 20            20 20         这种情况,就影响不变。        二:否则:田忌最慢的和国王最快的比 这里始终要把握的就一点: 要么就以最小的差值胜利,要么就以最大的差值输掉。 此谓贪心策略也。。。。 -----------------------------------------------------------

 

// 2660064 2010-07-22 15:36:38 Accepted 1052 31MS 200K 1713B C++ Tanky Woo 
// Author: Tanky Woo
// HDOJ 1052
#include 
#include 
using namespace std;

int num;
int tian[1000], king[1000];
// www.wutianqi.com
int cmp(int a, int b)   //按从小到大排序
{
    return a king[n])     //tian最慢的马比king最慢的马快
            {
                m++;
                n++;
                result++;
            }
            else if(tian[m] < king[n])     //tian最慢的马比king最慢的马慢,则和king最快的马比
            {
                m++;
                y--;
                result--;
            }
            else  //tian最慢的马比king最慢的一样快
            {
                if(tian[x] > king[y])   //tian最快的马比king最快的马快
                {
                    x--;
                    y--;
                    result++;
                }
                else if(tian[x] < king[y])   //tian最快的马比king最快的马慢,则tian最慢的和king最快的比
                {
                    m++;
                    y--;
                    result--;
                }
                else if(tian[x] == king[y])   //tian最快的马和king最快的马一样快
                {
                    if(tian[m] == king[y])   //如果tian最慢的马和king最快的一样,则不减
                    {
                        //如:
                        // 20 20
                        // 20 20
                        m++;
                        y--;
                    }
                    else if(tian[m] < king[y])
                    {
                        m++;
                        y--;
                        result--;
                    }
                }
            }
        }
        printf("%d\n", result*200);

    }
    return 0;
}