洛谷聪明质检员题解使用二分与前缀和

记录下首道绿色题目
原题 推荐使用洛谷平台查看题目，牛客平台的公式显示不够清晰
解题思路 ：采用二分法确定w的取值，二分的上限为最终石块的质量（通过遍历得出），下限为0。利用fan[]结构体数组保存每次需要检测的区间范围，针对每次二分的情况，首先使用前缀和数组a1[i]记录前i块符合要求的石头的价值（用于计算y值公式的第一个参数），再使用前缀和数组a2[i]记录前i块石头中符合要求的石头的数量（用于计算y值公式的第二个参数）。随后遍历fan[]结构体数组，计算p的数值，并通过筛选将最小的|p - s|赋给minn。若s大于p，则表明设定的标准值w过高，需调低标准以提升p的数值，即减小mid（此时mid已不符合条件，因此直接令rig = mid - 1）。若s小于p，则说明标准值过低，应提高mid（此时mid也不符合条件，因此直接令lef = mid + 1）

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 2e