本文主要是介绍POJ2287 HDU1052 Tian Ji -- The Horse Racing【贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://poj.org/problem?id=2287
http://acm.hdu.edu.cn/showproblem.php?pid=1052
题目大意：
田忌和大王赛马，两个人各有N匹马，每匹马都有一个速度，跑的快的胜，慢的就输。田忌每赢一
把得200，平了不得钱，输了输200。每次大王先出马，田忌再出马。问：田忌最多能得多少钱。
思路：
贪心思想。现对田忌和大王的马进行排序。田忌的马速度从小到大排列，大王的马速度从大到小排
列。为了尽可能的赢，田忌就要采取以下策略：
1)尽可能用自己速度低的马去赢得大王速度快的马。
2)剩下赢不了的马，尽可能用自己的马和大王的马打平手
3)剩下的既不能赢得比赛，也不能平手的马就只能是输了
用NumA[]数组和NumB[]数组分别标记已经知道胜负的马，遍历两次田忌和大王的马，第一次找出
能赢大王的马，第二次从剩下的马中找出能与大王的马平手的马。然后计算赢得的金钱。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;int A[1100],B[1100],NumA[1100],NumB[1100];int cmp(int a,int b)
{return a > b;
}int main()
{int N;while(~scanf("%d",&N) && N){for(int i = 0; i < N; ++i)scanf("%d",&A[i]);for(int i = 0; i < N; ++i)scanf("%d",&B[i]);sort(A,A+N);sort(B,B+N,cmp);memset(NumA,0,sizeof(NumA));memset(NumB,0,sizeof(NumB));//尽可能去赢for(int i = 0; i < N; ++i) //田忌{for(int j = 0; j < N; ++j) //国王{if(A[i] > B[j] && !NumA[i] && !NumB[j]){NumA[i] = 1;NumB[j] = 1;break;}}}//赢不了就尽可能平手for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){if(A[i] == B[j] && !NumA[i] && !NumB[j]){NumA[i] = 2;NumB[j] = 2;break;}}}int ans = 0;for(int i = 0; i < N; ++i)if(NumA[i] == 1)ans += 200;else if(NumA[i] == 2)continue;elseans -= 200;printf("%d\n",ans);}return 0;
}
这篇关于POJ2287 HDU1052 Tian Ji -- The Horse Racing【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
