BZOJ4045 : [Cerc2014] bricks

まずBとWの個数を求め,1種類しか現れなければsum(k)を直接出力する.
そうでなければ順次走査し,切断でき,時間複雑度$O(n)$である.
 

#include
#define N 100010
typedef 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
",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
",ans);
  }
  return 0;
}