P1650 田忌赛马

Lisa

显然的贪心思路就是用田忌最大的和齐王最大的进行比较,如果不能,就从小到大找到第一个没有贡献的马,用它换掉最大的

马,重复以上操作

什么叫没贡献的马,最弱的马和最弱的马进行比较,如果田忌的最弱的赢不了,他就是没贡献的

为什么不能简简单单的去最垃圾的马去换

这样可能造成不必要的浪费,既然他能做出贡献,有为什么要用来换呢

比如说对于这组数据

1 99 100

0 100 100

显然田忌是可以不输钱的,但是我们一味地用最小的马进行换的话,反而会输了200元

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
int a[10000001];
int b[10000001];
int main(){
	read(n);
	for(int i=1;i<=n;++i){
		read(a[i]);
	}
	for(int i=1;i<=n;++i){
		read(b[i]);
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int r=n;
	int ans=0;
	int l=1;
	int rr=n;
	int ll=1;
	while(ll<=rr){
		if(a[rr]>b[r]){
			rr--;
			r--;
			ans+=200;
		}else
				if(a[ll]>b[l]){
					ll++;
					l++;
					ans+=200;
				}else{
					if(a[ll]<b[r])
					ans-=200;
					ll++;
					r--;
				}
	}
	cout<<ans<<endl;
	return 0;
}
原文地址:https://www.cnblogs.com/For-Miku/p/15503446.html