欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ4045 : [Cerc2014] bricks

程序员文章站 2022-07-13 12:42:39
...

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

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

 

#include<cstdio>
#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\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;
}

  

上一篇: Java正则化

下一篇: dropout正则化