hdu 1052

題目大意：田忌的馬一定得比齊王的馬快才能贏，問n次比賽結束後田忌最多能贏多少錢！（注意：並不是同一等級的馬齊王一定比田忌快）;

解題思路：貪心.

貪心的策略：

一、當田忌最快的馬比國王最快的馬快時，用田忌最快的馬贏國王最快的馬。
二、當田忌最快的馬比國王最快的馬慢時，用田忌最慢的馬輸給國王最快的馬。
三、當田忌最快的馬跟國王最快的馬一樣快時，分情況。

所以：對於情況三，我們應該從最慢的馬開始考慮了

1、當田忌最慢的馬比國王最慢的馬快，那麼用田忌最慢的馬贏國王最慢的馬

2、當田忌最慢的馬比國王最慢的馬慢，那麼用田忌最慢的馬輸給國王最快的馬

3、當田忌最慢的馬跟國王最慢的馬相等的時候，用田忌最慢的馬跟國王最快的馬比

倒過來思考也是一樣的。。。
代碼如下：

 
/* 
 * 1052_3.cpp 
 * 
 *  Created on: 2013年8月10日 
 *      Author: Administrator 
 */  
  
#include <iostream>   
#include <algorithm>   
  
bool compare(int a, int b) {  
    return a < b;  
}  
using namespace std;  
int main() {  
    int n;  
    while (scanf("%d", &n) != EOF, n) {  
        int a[n], b[n];  
        int i, j;  
        for (i = 0; i < n; ++i) {  
            scanf("%d", &a[i]);  
        }  
  
        for (i = 0; i < n; ++i) {  
            scanf("%d", &b[i]);  
        }  
        sort(a, a + n);  
        sort(b, b + n);  
  
        int win = 0, kn = n;  
  
        for (i = 0, j = 0; i < n;) {  
            if (a[i] > b[j]) {  
//              printf("a[%d]=%d,b[%d]=%d\n",i,a[i],j,b[j]);   
//              cout<<"1"<<endl;   
                win++;  
                ++i;  
                ++j;  
            } else if (a[i] < b[j]) {  
//              cout<<"2"<<endl;   
                --win;  
                ++i;  
                --kn;  
            } else {  
//              cout<<"3"<<endl;   
                if (a[n - 1] > b[kn - 1]) {  
//                  cout<<"3_1"<<endl;   
                    ++win;  
                    --n;  
                    --kn;  
                } else if (a[n - 1] < b[kn - 1]) {  
//                  cout<<"3_2"<<endl;   
                    --win;  
                    ++i;  
                    --kn;  
                } else if (a[n - 1] == b[kn - 1]) {  
//                  cout<<"3_3"<<endl;   
                    if (a[i] < b[kn - 1]) {  
                        --win;  
                    }  
  
                    ++i;  
                    --kn;  
                }  
            }  
        }  
  
        printf("%d\n", win * 200);  
    }  
}  

/*
 * 1052_3.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */

#include <iostream>
#include <algorithm>

bool compare(int a, int b) {
	return a < b;
}
using namespace std;
int main() {
	int n;
	while (scanf("%d", &n) != EOF, n) {
		int a[n], b[n];
		int i, j;
		for (i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
		}

		for (i = 0; i < n; ++i) {
			scanf("%d", &b[i]);
		}
		sort(a, a + n);
		sort(b, b + n);

		int win = 0, kn = n;

		for (i = 0, j = 0; i < n;) {
			if (a[i] > b[j]) {
//				printf("a[%d]=%d,b[%d]=%d\n",i,a[i],j,b[j]);
//				cout<<"1"<<endl;
				win++;
				++i;
				++j;
			} else if (a[i] < b[j]) {
//				cout<<"2"<<endl;
				--win;
				++i;
				--kn;
			} else {
//				cout<<"3"<<endl;
				if (a[n - 1] > b[kn - 1]) {
//					cout<<"3_1"<<endl;
					++win;
					--n;
					--kn;
				} else if (a[n - 1] < b[kn - 1]) {
//					cout<<"3_2"<<endl;
					--win;
					++i;
					--kn;
				} else if (a[n - 1] == b[kn - 1]) {
//					cout<<"3_3"<<endl;
					if (a[i] < b[kn - 1]) {
						--win;
					}

					++i;
					--kn;
				}
			}
		}

		printf("%d\n", win * 200);
	}
}


以上附上另外一篇博客的地址。算法都是一樣的。但他的代碼有注釋。在這裡我就懶得寫注釋了。。