[Bzoj1034][ZJOI2008]泡泡堂BNB（贪心）

Description

Solution

这题就是一个贪心，

如果最弱的能赢对方最弱的就赢

否则最强的能赢对面最强的就赢

否则最弱的换对面最强

Code

#include <cstdio>

#include <algorithm>

using namespace std;

int n,Ans,A[100010],B[100010];

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void solve(int f){

	Ans=0;

	int la=1,ra=n,lb=1,rb=n;

	while(la<=ra&&lb<=rb){

		if(A[la]>B[lb]) Ans+=2,la++,lb++;

		else if(A[ra]>B[rb]) Ans+=2,ra--,rb--;

		else{

			if(A[la]==B[rb]) Ans++;

			la++,rb--;

		}

	}

	if(!f)swap(A,B),printf("%d ",Ans);

	else printf("%d\n",2*n-Ans);

}

int main(){

	n=read();

	for(int i=1;i<=n;++i)A[i]=read();

	for(int i=1;i<=n;++i)B[i]=read();

	sort(A+1,A+n+1);sort(B+1,B+n+1);

	solve(0);solve(1);

	return 0;

}

巴特西

[Bzoj1034][ZJOI2008]泡泡堂BNB（贪心）

Description

Solution

Code

最新文章

热门文章