比赛 20120302 评测结果 AAWWWWWWWW
题目名称 田忌赛马 最终得分 20
用户昵称 Makazeu 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-02 21:45:34
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef short int sint;
const int MAXN=5101;
const int INF=10001;
int HorA[MAXN];
int HorB[MAXN];
int N;
sint F[MAXN][MAXN];
sint G[MAXN][MAXN];

int cmp(const void *a,const void *b)
{
	return *((int *)b)-*((int *)a);
}

void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++) scanf("%d",&HorA[i]);
	for(int i=1;i<=N;i++) scanf("%d",&HorB[i]);
	qsort(HorA+1,N,sizeof(HorA[0]),cmp);
	qsort(HorB+1,N,sizeof(HorB[0]),cmp);
	
	/*
	for(int i=1;i<=N;i++) printf("%d ",HorA[i]);
	printf("\n");
	for(int i=1;i<=N;i++) printf("%d ",HorB[i]);
	*/
}

sint Max(sint a,sint b)
{
	return a>b?a:b;
}

/*
void dp()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			if(HorB[i]>HorA[j]) G[i][j]=1;
			if(HorB[i]==HorA[j]) G[i][j]=0;
			if(HorB[i]<HorA[j]) G[i][j]=-1;
		}
	}
	
	//for(int i=0;i<=N;i++)
		//F[0][i]=0;
	F[0][0]=0;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			F[i][j]=-INF;
	int tmp;
	int max;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=i;j++)
		{
			max=-INF;
			tmp=F[i-1][j]+G[N-(i-j)][i];
			max=Max(max,tmp);
			tmp=F[i-1][j-1]+G[j][i];
			max=Max(max,tmp);
			F[i][j]=max;
		}
	}		
	int Ans=0;
	for(int i=1;i<=N;i++)
		Ans=Max(Ans,F[N][i]);
	printf("%d\n",Ans);
}
*/

void Greedy()
{
	int Ans=0;
	int Tot=0;
	int AS=1,AE=N;
	int BS=1,BE=N;
	int Tt,Tq;
	for(;Tot<N;Tot++)
	{
		Tt=HorB[BS];
		Tq=HorA[AS];
		if(Tt>Tq)
		{
			Ans++;
			BS++;
			AS++;
			continue;
		}
		if(Tt<Tq)
		{
			Ans--;
			BE--;
			AS++;
			continue;
		}
		BE--;
		AS++;
		if(HorB[BE]<HorA[AS]) Ans--;
		if(HorB[BE]==HorA[AS]) Ans=Ans;
	}
	printf("%d\n",Ans);
}

int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	init();
	Greedy();
	return 0;
}