[NOIP模拟]小x分砖块

砖块"/>

[NOIP模拟]小x分砖块

ASDFZ-NOIP2016 模拟
题目：
问题描述
小 X 喜欢跟着爸爸跑到建筑工地上去。
这天，小 X看到一排砖，每块要么是白色的（0），要么是黑色的（1）。小 X 想把这排砖分成若干非空段，使得每段白砖和黑砖块数的比例相同。
当然，小 X可以直接把整排砖作为一段，那就太简单了。为了增加难度，小 X 想知道最多能分成多少段，例如：100011 = 10 + 0011（即样例 1，最多分成 2 段，比例为 1:1）；0001110000000001 = 0001 + 11000000 + 0001（即样例 2，最多分成 3段，比例为 3:1） 。小 X 百思不得其解，希望你帮帮他。
输入格式
第一行包含一个整数 N。我们将用 N 行来描述这排砖，初始时这排砖为空。接下来 N 行，每行包含用一个空格隔开的两个整数 Ki,Ci（Ci 只可能是 0 或 1），表示在上一行描述完后尾部又有了 Ki 块颜色为 Ci 的砖。
输出格式
第一行包含一个整数，表示最多能分成的段数。
样例输入 1
3
1 1
3 0
2 1
样例输出 1
2
样例输入 2
4
3 0
3 1
9 0
1 1
样例输出 2
3
数据范围
对于 30%的数据，N=1。
对于 60%的数据，所有 Ki均相等。
对于 100%的数据， 1≤N≤100000， 1≤Ki≤1000000000， 砖的总块数不超过 1000000000。
分析
因为每一个按相同比例分，所以总的比例一定。所以可以先算出最简比，加起来得到一段的至少得块数，每一段比是这块数的倍数。再从头扫到尾，看能分出多少段。这道题本来很简单，但是考试时犯了两个错误，导致只得了40分。1、关于计算此时的倍数，更新位置没放对。2、判断不满足比例时，应该是break，而不是continue。
附代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<iomanip>
#include<cmath>
#include<cctype>
#include<set>
#include<algorithm>
using namespace std;int n,ans;
long long num,num1,num0,tot,tot0,tot1;struct node{int k;int c;
}a[100100];inline int readint()
{char ch;int i=0,f=1;for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());if(ch=='-'){f=-1;ch=getchar();}for(;ch>='0'&&ch<='9';ch=getchar())i=(i<<3)+(i<<1)+ch-'0';return i*f;
}inline int find(int x,int y)
{int b;if(x<y) swap(x,y);while(x%y!=0){b=x%y;x=y;y=b;}return y;
}int main()
{//freopen("brick.in","r",stdin);//freopen("brick.out","w",stdout);n=readint();for(int i=1;i<=n;i++){a[i].k=readint();a[i].c=readint();if(a[i].c==0) num0+=a[i].k;else num1+=a[i].k;}if(n==1){printf("%d",a[1].k);}else{if(num0==0||num1==0){ans=num0+num1;printf("%d",ans);return 0;}int gys=find(num0,num1);num0=num0/gys;num1=num1/gys;num=num0+num1;int d=0;for(int i=1;i<=n;i++){int t=d,bz=3;tot+=a[i].k;if(a[i].c==0) tot0+=a[i].k;else tot1+=a[i].k;if((d==0&&tot>=num)||(d!=0&&tot>=num*d)){do{++t;int cha=tot-num*t;if(tot==0||tot1==0) {d=tot/num;break;}if(cha<0) break;d=t;if(a[i].c==0) tot0=tot0-cha;else tot1=tot1-cha;if(tot0*num1==tot1*num0) {ans++;tot=tot0=tot1=0;tot=cha;bz=0;d=0;}if(a[i].c==0) tot0=tot0+cha;else tot1=tot1+cha;if(bz!=0&&(tot-num*t>=num)) bz=1;}while(bz==1);}}   printf("%d",ans);}return 0;
}