首先求出B和W的个数，如果只出现了一种那么直接输出sum(k)。

否则依次扫描，能割就割，时间复杂度$O(n)$。

 

#include
     
      #define N 100010typedef long long ll;int T,n,i,a[N],b[N],c[2],d[2],ans;ll x;char s[2];int main(){  scanf("%d",&T);  while(T--){    scanf("%d",&n);    c[0]=c[1]=d[0]=d[1]=ans=0;    for(i=1;i<=n;i++)scanf("%d%s",&b[i],s),a[i]=s[0]=='B',c[a[i]=s[0]=='B']+=b[i];    if(!c[0]||!c[1]){printf("%d\n",c[0]+c[1]);continue;}    for(i=1;i<=n;i++){      x=(ll)c[a[i]]*d[a[i]^1]-(ll)d[a[i]]*c[a[i]^1];      if(x%c[a[i]^1]||x<=0||x/c[a[i]^1]>b[i])d[a[i]]+=b[i];      else ans++,d[a[i]]=b[i]-x/c[a[i]^1],d[a[i]^1]=0;    }    printf("%d\n",ans);  }  return 0;}