MyException - 我的异常网
当前位置:我的异常网» 编程 » hdu - 1052 - Tian Ji - The Horse Racing

hdu - 1052 - Tian Ji - The Horse Racing

www.MyException.Cn  网友分享于:2013-02-21  浏览:5次
hdu - 1052 - Tian Ji -- The Horse Racing

题意:田忌与齐感威王赛马,每人n(n <= 1000)只马,接着输入田忌n只马的速度,再输入齐威王n只马的的速度,每胜一场得200金币,输一场赔200金币,问田忌最多能得到多少金币(当然,开始时两人的金币都是0)。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1052

——>>有点递归的思想,先处理两人最快的马(或者最慢的马,或者最快与最慢的马,不过都是1人1匹),然后对剩下的n-1只应用同样的策略,直到最后所有的马都比较完。

贪心策略如下:

while(t_best >= t_worst){

田忌最快的马 比 齐威王最快的马

        让它们赛一都场

 田忌最快的马 比 齐威王最快的马

        田忌用最慢的马去赛齐威王最快的马

田忌最快的马 比 齐威王最快的马 一样快

        当 田忌最慢的马 比齐威王最慢的马 快 时

                让这两匹最慢的马赛一场, 回到while顶部

        否则

田忌用最慢的马去赛齐威王最快的马

}

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1000 + 10;

int main()
{
    int t[maxn], k[maxn], n, i;
    while(~scanf("%d", &n))
    {
        if(!n) return 0;
        for(i = 0; i < n; i++) scanf("%d", &t[i]);
        for(i = 0; i < n; i++) scanf("%d", &k[i]);
        sort(t, t+n);
        sort(k, k+n);
        int t_best = n-1, t_worst = 0, k_best = n-1, k_worst = 0;
        while(t_best >= t_worst)
        {
            if(t[t_best] > k[k_best])
            {
                t[t_best--] = -1;
                k_best--;
            }
            else if(t[t_best] < k[k_best])
            {
                t[t_worst++] = -2;
                k_best--;
            }
            else
            {
                if(t[t_worst] > k[k_worst])
                {
                    t[t_worst++] = -1;
                    k_worst++;
                }
                else
                {
                    if(t[t_worst] == k[k_best])
                    {
                        t_worst++;
                        k_best--;
                    }
                    else
                    {
                        t[t_worst++] = -2;
                        k_best--;
                    }
                }
            }
        }
        int sum_y = 0, sum_n = 0;
        for(i = 0; i < n; i++)
        if(t[i] == -1) sum_y++;
        else if(t[i] == -2) sum_n++;
        printf("%d\n", (sum_y-sum_n)*200);
    }
    return 0;
}



文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有