比赛 2024暑假C班集训C 评测结果 AAAAAAAAAA
题目名称 W&B 最终得分 100
用户昵称 liuyiche 运行时间 1.602 s
代码语言 C++ 内存使用 3.55 MiB
提交时间 2024-07-12 09:12:35
显示代码纯文本
#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

int t, n;

struct node
{
    bool cl;
    int cnt;    
};
vector<node> v(100005);
    
int main()
{
    freopen("silly.in", "r", stdin);
    freopen("silly.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> t;
    while(t--)
    {
        cin >> n;
        int cnt1 = 0, cnt0 = 0, ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            int k;
            char c;
            cin >> k >> c;
            if(c == 'B')
                v[i].cl = 1, cnt1 += k;
            else
                v[i].cl = 0, cnt0 += k;
            v[i].cnt = k;
        }
        if(cnt1 == 0 || cnt0 == 0)
        {
            cout << max(cnt1,cnt0) << '\n';
            continue;
        }
        int q = __gcd(cnt1,cnt0);
        cnt1 /= q, cnt0 /= q;
        //cout << cnt1 << " : " << cnt0 << '\n'; 
        int tmp1 = 0, tmp0 = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(v[i].cl == 1)
            {
                if(tmp0 != 0 && tmp0%cnt0 == 0 && tmp0/cnt0*cnt1 >= tmp1)
                {
                    int tt = min(v[i].cnt,tmp0/cnt0*cnt1-tmp1);
                    v[i].cnt -= tt;
                    tmp1 += tt;
                    if(tmp1 == tmp0/cnt0*cnt1)
                    {
                        tmp1 = 0, tmp0 = 0;
                        ans++;
                    }
                    tmp1 += v[i].cnt;   
                }
                else
                    tmp1 += v[i].cnt;
            }
            else
            {
                if(tmp1 != 0 && tmp1%cnt1 == 0 && tmp1/cnt1*cnt0 >= tmp0)
                {
                    int tt = min(v[i].cnt,tmp1/cnt1*cnt0-tmp0);
                    v[i].cnt -= tt;
                    tmp0 += tt;
                    if(tmp0 == tmp1/cnt1*cnt0)
                    {
                        tmp1 = 0, tmp0 = 0;
                        ans++;
                    }
                    tmp0 += v[i].cnt;   
                }
                else
                    tmp0 += v[i].cnt;
            }
            //cout << tmp1 << " " << tmp0 << '\n';
        }
        cout << ans << '\n';
    }
    
   	return 0;
}