noi.ac #227 random

分析

我们发现实际只要计算a[i]>b[j]和a[i]<b[j]哪种多即可

代码

#include<bits/stdc++.h>
using namespace std;
int a[100100],b[100100],n,Ans,le,ri;
int main(){
    int i,j,k,t;
    scanf("%d",&t);
    while(t--){
      Ans=0,le=0;
      scanf("%d",&n);
      for(i=1;i<=n;i++)scanf("%d",&a[i]);
      for(i=1;i<=n;i++)scanf("%d",&b[i]);
      sort(a+1,a+n+1);
      sort(b+1,b+n+1);
      for(i=1;i<=n;i++){
          while(le<=n&&b[le+1]<a[i])le++;
          ri=le;
          while(ri<=n&&b[ri+1]==a[i])ri++;
          Ans+=le+ri-n;
      }
      if(Ans>0)puts("Alice");
        else if(Ans<0)puts("Bob");
        else puts("Tie");
    }
    return 0;
}