【题解】BZOJ1034 [ZJOI2008]泡泡堂BNB(贪心)

考虑直接模拟田忌赛马...

我的最小比你的大，直接上
我的最大比你的大，直接上
otherwise，我小换你大

考虑最劣，由于每次比赛会产生且仅会产生\(2\)个积分，所以swap两个数组然后输出\(2n-ans\)即可。

实现的时候注意一次循环内只能产生一次比拼，不然可能导致一个人重复比赛两次...

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=1e6+5;

int data1[maxn],data2[maxn],n;

inline int getp(const int&x,const int&y){

      if(x>y)return 2;

      if(x==y)return 1;

      return 0;

}

inline int getans(int*a,int*b){

      int L1=1,L2=n,R1=1,R2=n,ret=0;

      while(L1<=L2&&R1<=R2){

	    if(a[L2]>b[R2]) ret+=2,L2--,R2--;

	    else if(a[L1]>b[R1]) ret+=2,L1++,R1++;

	    else ret+=(a[L1]==b[R2]),L1++,R2--;

      }

      return ret;

}

int main(){

      n=qr();

      for(int t=1;t<=n;++t)data1[t]=qr();

      for(int t=1;t<=n;++t)data2[t]=qr();

      sort(data1+1,data1+n+1);

      sort(data2+1,data2+n+1);

      printf("%d %d\n",getans(data1,data2),2*n-getans(data2,data1));

      return 0;

}

巴特西

【题解】BZOJ1034 [ZJOI2008]泡泡堂BNB(贪心)

【题解】BZOJ1034 [ZJOI2008]泡泡堂BNB(贪心)

最新文章

热门文章