比赛 2024暑假C班集训C 评测结果 AAAAAAAAAA
题目名称 W&B 最终得分 100
用户昵称 liuyiche 运行时间 1.602 s
代码语言 C++ 内存使用 3.55 MiB
提交时间 2024-07-12 09:12:35
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int t, n;
  7.  
  8. struct node
  9. {
  10. bool cl;
  11. int cnt;
  12. };
  13. vector<node> v(100005);
  14. int main()
  15. {
  16. freopen("silly.in", "r", stdin);
  17. freopen("silly.out", "w", stdout);
  18. ios::sync_with_stdio(false);
  19. cin.tie(0); cout.tie(0);
  20. cin >> t;
  21. while(t--)
  22. {
  23. cin >> n;
  24. int cnt1 = 0, cnt0 = 0, ans = 0;
  25. for(int i = 1; i <= n; ++i)
  26. {
  27. int k;
  28. char c;
  29. cin >> k >> c;
  30. if(c == 'B')
  31. v[i].cl = 1, cnt1 += k;
  32. else
  33. v[i].cl = 0, cnt0 += k;
  34. v[i].cnt = k;
  35. }
  36. if(cnt1 == 0 || cnt0 == 0)
  37. {
  38. cout << max(cnt1,cnt0) << '\n';
  39. continue;
  40. }
  41. int q = __gcd(cnt1,cnt0);
  42. cnt1 /= q, cnt0 /= q;
  43. //cout << cnt1 << " : " << cnt0 << '\n';
  44. int tmp1 = 0, tmp0 = 0;
  45. for(int i = 1; i <= n; ++i)
  46. {
  47. if(v[i].cl == 1)
  48. {
  49. if(tmp0 != 0 && tmp0%cnt0 == 0 && tmp0/cnt0*cnt1 >= tmp1)
  50. {
  51. int tt = min(v[i].cnt,tmp0/cnt0*cnt1-tmp1);
  52. v[i].cnt -= tt;
  53. tmp1 += tt;
  54. if(tmp1 == tmp0/cnt0*cnt1)
  55. {
  56. tmp1 = 0, tmp0 = 0;
  57. ans++;
  58. }
  59. tmp1 += v[i].cnt;
  60. }
  61. else
  62. tmp1 += v[i].cnt;
  63. }
  64. else
  65. {
  66. if(tmp1 != 0 && tmp1%cnt1 == 0 && tmp1/cnt1*cnt0 >= tmp0)
  67. {
  68. int tt = min(v[i].cnt,tmp1/cnt1*cnt0-tmp0);
  69. v[i].cnt -= tt;
  70. tmp0 += tt;
  71. if(tmp0 == tmp1/cnt1*cnt0)
  72. {
  73. tmp1 = 0, tmp0 = 0;
  74. ans++;
  75. }
  76. tmp0 += v[i].cnt;
  77. }
  78. else
  79. tmp0 += v[i].cnt;
  80. }
  81. //cout << tmp1 << " " << tmp0 << '\n';
  82. }
  83. cout << ans << '\n';
  84. }
  85. return 0;
  86. }
  87.