比赛 |
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;
}