[BZOJ 1034][ZJOI 2008]泡堂BNB(類田忌競馬欲張り)

1169 ワード

http://www.lydsy.com:808/JudgeOnline/problem.php?id=1034
これはつまり版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; }