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);
	}
}


以上附上另外一篇博客的地址。算法都是一样的。但他的代码有注释。在这里我就懒得写注释了。。

补充：软件开发 , C++ ,

上一个：POJ 3264 Balanced Lineup 线段树
下一个：POJ3690+位运算