首页 > 代码库 > LA 3266 (贪心) Tian Ji -- The Horse Racing
LA 3266 (贪心) Tian Ji -- The Horse Racing
题意：
田忌和齐王各有n匹马，如果马的速度比齐王的快就赢200，慢则输200，相等不赔不赚。
已知两人每匹马的速度(为整数)和齐王所排出的马的顺序，问田忌该如何应对才能使收益最大。
分析：
本以为是一道很简单的贪心，上来就贪，结果什么都没贪出来。
看了题解才发现贪心是比较复杂的。
这里贴上poj某牛的神分析。
贪心策略：1，如果田忌的最快马快于齐王的最快马，则两者比。（因为若是田忌的别的马很可能就赢不了了，所以两者比）2，如果田忌的最快马慢于齐王的最快马，则用田忌的最慢马和齐王的最快马比。（由于所有的马都赢不了齐王的最快马，所以用损失最小的，拿最慢的和他比）3，若相等，则比较田忌的最慢马和齐王的最慢马3.1，若田忌最慢马快于齐王最慢马，两者比。（田忌的最慢马既然能赢一个就赢呗，而且齐王的最慢马肯定也得有个和他比，所以选最小的比他快得。）3.2，其他，则拿田忌的最慢马和齐王的最快马比。（反正所有的马都比田忌的最慢马快了，所以这匹马必输，选贡献最大的，干掉齐王的最快马）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 1000 + 10; 6 int tian[maxn], king[maxn]; 7 8 int main(void) 9 {10 //freopen("3266in.txt", "r", stdin);11 int n;12 while(scanf("%d", &n) == 1 && n)13 {14 for(int i = 0; i < n; ++i) scanf("%d", &tian[i]);15 for(int i = 0; i < n; ++i) scanf("%d", &king[i]);16 sort(tian, tian + n);17 sort(king, king + n);18 19 int thead = 0, khead = 0;20 int ttail = n-1, ktail = n-1;21 int win = 0;22 23 while(n--)24 {25 if(tian[ttail] > king[ktail]) //Èç¹ûÌï¼ÉµÄ×î¿ìÂí¿ìÓÚÆëÍõµÄ×î¿ìÂí£¬ÔòÁ½Õ߱ȡ£26 {27 ttail--;28 ktail--;29 win++;30 }31 else if(tian[ttail] < king[ktail]) //Èç¹ûÌï¼ÉµÄ×î¿ìÂíÂýÓÚÆëÍõµÄ×î¿ìÂí£¬ÔòÓÃÌï¼ÉµÄ×îÂýÂíºÍÆëÍõµÄ×î¿ìÂí±È¡£32 {33 thead++;34 ktail--;35 win--;36 }37 else //ÈôÏàµÈ£¬Ôò±È½ÏÌï¼ÉµÄ×îÂýÂíºÍÆëÍõµÄ×îÂýÂí38 {39 if(tian[thead] > king[khead]) //ÈôÌï¼É×îÂýÂí¿ìÓÚÆëÍõ×îÂýÂí£¬Á½Õ߱ȡ£40 {41 thead++;42 khead++;43 win++;44 }45 else //ÆäËû£¬ÔòÄÃÌï¼ÉµÄ×îÂýÂíºÍÆëÍõµÄ×î¿ìÂí±È¡£46 {47 if(tian[thead] < king[ktail]) win--;48 thead++;49 ktail--;50 }51 }52 }53 54 printf("%d\n", win * 200);55 }56 57 return 0;58 }
LA 3266 (贪心) Tian Ji -- The Horse Racing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。