[BZOJ 1034][ZJOI 2008]泡堂BNB(類田忌競馬欲張り)
1169 ワード
http://www.lydsy.com:808/JudgeOnline/problem.php?id=1034
これはつまり版POJを変えたあのTianji the horse racingですか?
でも、この問題のゲームのルールはちょっと違っています.勝ちは2点、引き分けは1点、負けは減点しません.だから、欲張りの過程とPOJの問題は少し違っています.具体的にコードを見ましょう.
これはつまり版POJを変えたあのTianji the horse racingですか?
でも、この問題のゲームのルールはちょっと違っています.勝ちは2点、引き分けは1点、負けは減点しません.だから、欲張りの過程とPOJの問題は少し違っています.具体的にコードを見ましょう.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 100050
using namespace std;
int a[MAXN],b[MAXN],n;
int cal() // :cal a , a
{
int minpa=1,minpb=1,maxpa=n,maxpb=n,ans=0; //a 、b 、a 、b
while(minpa<=maxpa)
{
if(a[minpa]>b[minpb]) ans+=2,minpa++,minpb++; //a b , a b
else if(a[maxpa]>b[maxpb]) ans+=2,maxpa--,maxpb--; //a b
else ans+=(a[minpa]==b[maxpb]),minpa++,maxpb--; // a b
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
printf("%d ",cal());
swap(a,b);
printf("%d
",2*n-cal());
return 0;
}