• C. Left and Right Houses


    本题链接:Problem - C - Codeforces

    题目:

    样例:

    输入
    1. 7
    2. 3
    3. 101
    4. 6
    5. 010111
    6. 6
    7. 011001
    8. 3
    9. 000
    10. 3
    11. 110
    12. 3
    13. 001
    14. 4
    15. 1100

    输出
    2
    3
    2
    3
    0
    1
    0

    思路:

            根据题目意思。

            寻找一条道路进行分割该字符串,设该道路分割位置为 i  ,使得满足以下条件:

            1、左侧有  \left \lceil \frac{i}{2} \right \rceil  个  0,右侧有 \left \lceil \frac{n - i}{2} \right \rceil 个 1

            2、如果有多个位置满足 条件一,我们就要选择最小的位置 \left | \frac{n}{2} - i \right |.

            读懂意思后,暴力枚举一遍即可。通过前缀和记录每个位置 1 的数量,遍历判断以下即可。

    代码详解如下:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define endl '\n'
    8. #define int long long
    9. #define YES puts("YES")
    10. #define NO puts("NO")
    11. #define umap unordered_map
    12. #define All(x) x.begin(),x.end()
    13. #pragma GCC optimize(3,"Ofast","inline")
    14. #define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
    15. using namespace std;
    16. const int N = 2e6 + 10;
    17. inline void solve();
    18. signed main()
    19. {
    20. // freopen("a.txt", "r", stdin);
    21. IOS;
    22. int _t = 1;
    23. cin >> _t;
    24. while (_t--)
    25. {
    26. solve();
    27. }
    28. return 0;
    29. }
    30. inline void solve()
    31. {
    32. string s;
    33. int n,ans = -1;
    34. cin >> n >> s;
    35. vector<int>sum(n + 10,0);
    36. // 这里是根据前缀和记录相应位置 1 的数量
    37. // 这里从下标 1 开始记录的前缀和数量,是由于 道路有可能会在最左侧。
    38. for(int i = 1;i <= n;++i)
    39. {
    40. sum[i] = sum[i - 1] + bool(s[i - 1] == '1');
    41. }
    42. // 开始遍历判断 这里 i <= n 是有可能道路也会在最右侧
    43. for(int i = 0;i <= n;++i)
    44. {
    45. // 如果 道路是 i 的时候,左侧 1 的数量没有超过 i / 2 说明 左侧至少有 i / 2 个 0
    46. // 并且 右侧 1 的个数 >= (n - i) / 2 那么满足了 条件一
    47. if((sum[i] << 1) <= i and ((sum[n] - sum[i]) << 1) >= n - i)
    48. {
    49. // 这里是判断寻找最小化位置 |n / 2 - i|
    50. if(abs(n - (i << 1)) < abs(n - (ans << 1))) ans = i;
    51. }
    52. }
    53. cout << ans << endl;
    54. }

    最后提交:

  • 相关阅读:
    【datawhale202206】pyTorch推荐系统:多任务学习 ESMM&MMOE
    03初始Docker
    外贸企业都要知道的8个外贸网站推广平台!
    不讲故事的设计模式-责任链模式
    npm常用命令详解(二)
    [NOIP2010 普及组] 三国游戏
    F- Kobolds and Catacombs_gov
    第五章 树 6 AcWing 1576. 再次树遍历
    Flink学习4 - 富函数 + 数据重分区操作 + sink 操作(kafka、redis、jdbc)
    JVM基础面试题
  • 原文地址:https://blog.csdn.net/hacker_51/article/details/138193476