hdoj 1052 Tian Ji -- The Horse Racing 贪心算法

这道题就是解决选择策略问题。

思路一:

先将田忌跟齐王的马的速度数组进行一次冒泡排序

1、如果田忌最慢的马比齐王最慢的马快，则比慢马

2、如果田忌最慢的马比齐王最慢的马慢，则用田最慢的马跟齐最快的马比  //消耗齐的快马这是贪心的第一步

3、如果田忌最慢的马的速度与齐威王最慢的马速度相等

    3.1、如果田忌最快马的比齐威王最快的快，则比快马                         //这是贪心的第二步

    3.2、如果田忌最快马比齐威王最快的慢，田忌慢VS齐王快

    3.3、如果田忌最快马比齐威王最快的相等，田忌慢VS齐王快

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1010],b[1010];
int main()
{
    int n,i,awin,bwin,afast,bfast,aslow,bslow;
    while(scanf("%d",&n)&&n)
    {
        for(i=0;i<n;++i)
            scanf("%d",&a[i]);//tian的马
        for(i=0;i<n;++i)
            scanf("%d",&b[i]);

        sort(a,a+n);//从小到大
        sort(b,b+n);

        awin=bwin=0;//记录赢的次数
        afast=bfast=n-1;//标记最快的马
        aslow=bslow=0;//标记最慢的马

        for(i=0;i<n;++i)
        {
            if(a[aslow]>b[bslow]) //tian的慢马 大于 king的慢马
            {
                awin++;  //tian胜利
                aslow++; //tian的马
                bslow++; //king的马
            }
            else if(a[aslow]<b[bslow]) //用最慢马消耗国王的最快马
            {
                bwin++; //king胜利
                aslow++;
                bfast--;
            }
            else//两匹最慢马速度相同时
            {
                if(a[afast]>b[bfast])   //tian的快马 大于 king的快马
                {
                    awin++;
                    afast--;
                    bfast--;
                }
                else if(a[aslow]<b[bfast])  //如果田忌的最快马不能胜国王的最快马，则用慢马消耗
                {
                    bwin++;
                    aslow++;
                    bfast--;
                }
            }
        }
        printf("%d\n",200*(awin-bwin));
    }
    return 0;
}

思路二:

先将田忌跟齐王的马的速度数组进行一次冒泡排序

1、如果田忌最快的马比齐王最快的马快，则快马比

2、如果田忌最快的马比齐王最快的马慢，则用田最慢的马跟齐最快的马比  //这是贪心的第一步

3、如果田忌最快的马的速度与齐威王最快的马速度相等

  3.1、如果田忌最慢的比齐威王最慢的快，则慢马比                        //这是贪心的第二步

  3.2、如果田忌最慢的比齐威王最慢的慢，田忌慢VS齐王快（这里要判断田忌慢马和齐王快马速度是否相等）

  3.3、田忌最慢的与齐威王最慢的相等，田忌慢VS齐王快（这里要判断田忌慢马和齐王快马速度是否相等）

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <stdio.h>

using namespace std;

bool compare(int a, int b) {
    return a < b;   //从小到大排序
}

int main() {
    int n;
    int sum = 0;
    int tj[1000] = {0};
    int gw[1000] = {0};
    while (cin >> n && n) {
        sum = 0;
        tj[1000]={0};
        gw[1000]={0};
        for (int j = 0; j < n; j++) {
            cin >> tj[j];
        }
        for (int j = 0; j < n; j++) {
            cin >> gw[j];
        }
        sort(tj, tj + n, compare);
        sort(gw, gw + n, compare);

        int tj1 = 0, tj2 = n - 1;//比较指针
        int gw1 = 0, gw2 = n - 1;

        while (n--) {
            if (tj[tj2] < gw[gw2]) {  // 比国王的慢
                gw2--;
                tj1++;
                sum=sum-200;
                continue;
            }
            if (tj[tj2] > gw[gw2]) {  // 比国王的快
                gw2--;
                tj2--;
                sum=sum+200;
                continue;
            }
            if (tj[tj2] = gw[gw2]) {  // 和国王的一样
                if(tj[tj1] <= gw[gw1]){  //田 最慢的比国王 最慢的 慢
                    if(tj[tj1] != gw[gw2]){  //注意：田忌慢马和齐王快马速度是否相等
                        sum=sum-200;
                    }
                    gw2--;       //田用慢的比
                    tj1++;
                    continue;
                }
                if(tj[tj1] > gw[gw1]){  //田 最慢的比国王 最慢的 快
                    sum=sum+200;
                    tj1++;      //田用快的比
                    gw1++;

                    continue;
                }
            }
        }
        cout << sum << endl;
    }
    return 0;
}