田忌赛马 贪心

思路:
先排序,然后比较,比较分以下情况。

田忌最快的马比王的快,可以直接赢下他,此时收益最大
田忌最快的马不如王的快,则此时是必输局面,用最慢的马输给他,为后续比较提供更大的胜算

田忌最快的马和王的一样快,比较最慢的马
分三种情况
田忌最慢的马比王的快,则用最慢的马赢王最慢的马,收益最大
田忌最慢的马比王的慢,又是一个必输局面,用最慢的马输王最快的马,为后续提供更多胜算
田忌最慢的马和王的一样慢,用最慢的马输与王比(可能输也可能平局),为后续比较提供更多胜算

然后模拟就好了

emm,答案可能是负数,我用了快速输入输出,在输出的时候没考虑到这一点,因此wa了好多发。

#include<cstdio>
//using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
int p(int a[], int l, int r){
	int s = a[l];
	int i, j;
	i = l;
	j = r;
	while (i < j){
		while (i < j && a[j] >= s)j--;
		if (i < j)a[i++] = a[j];
		while (i < j && a[i] < s)i++;
		if (i < j)a[j--] = a[i];
	}
	a[i] = s;
	return i;
}
void sort(int a[], int l, int r){
	if (l < r){
		int k = p(a, l, r);
		sort(a, l, k - 1);
		sort(a, k + 1, r);
	}
}
template <class T>
bool read(T & a){
	a = 0;
	int flag = 0;
	char ch;
	if((ch = getchar()) == '-'){
		flag = 1;
	}
	else if(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
	}
	while ((ch = getchar()) >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
	}
	if(flag)a = -a;
	return true;
}
template <class T, class ... R>
bool read(T & a, R & ... b){
	if(!read(a))return 0;
	read(b...);
}
template <class T>
bool out(T a){
	if(a < 0)putchar('-');
	if(a >= 10)out(a / 10);
	putchar(a % 10 + '0');
	return true;
}
template <class T, class ... R>
bool out(T a, R ... b){
	if(!out(a))return 0;
	out(b...);
}
int n;
int a[1100], b[1100];
void in(){
	rep (i, 0, n - 1){
		read(a[i]);
	}
	rep (i, 0, n - 1){
		read(b[i]);
	}
}
void solve(){
	int ans = 0;
	sort(a, 0, n - 1);
	sort(b, 0, n - 1);
	int la, lb, ra, rb;
	la = lb = 0;
	ra = rb = n - 1;
	rep (i, 0, n - 1){
		if (a[ra] > b[rb]){
			ans += 200;
			ra--;
			rb--;
		}
		else if (a[ra] < b[rb]){
			ans -= 200;
			rb--;
			la++;
		}
		else {
			if (a[la] < b[lb]){
				la++;
				rb--;
				ans -= 200;
			}
			else if (a[la] > b[lb]){
				la++;
				lb++;
				ans += 200;
			}
			else {
				if (a[la] < b[rb])ans -= 200;
				la++;
				rb--;
			}
		}
	}
	if (ans < 0){
		putchar('-');
		ans = -ans;
	}
	out(ans);puts("");
}
int main(){
	while (read(n) && n){
		in();
		solve();
	}
	return 0;
} 
上一篇:高阶数据结构与算法 | RB_Tree(红黑树)的实现


下一篇:Error:Execution failed for task ':app:transformClassesWithDexForDebug'解决记录