I - The old Padawan Gym - 100285I——二分查找

Dear 丶 2022-06-10 05:18 104阅读 0赞

Think:  
1知识点：二分查找+前缀和  
2题意：n个石子，m次发呆，每次发呆若手中石子足够掉落石子大于k，询问将所有石子拾到手中所需要的时间  
3反思：多理解，多反思，多思考

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    LL sum[101400], tmp[101400];
    
    int Bin_pos(int l, int r, int x);/*二分查找小于x的第一个数的位置，区间[l, r]越界则返回0*/
    
    int main(){
        int n, m, k, x, i, pos, ans;
        while(~scanf("%d %d %d", &n, &m, &k)){
            scanf("%lld", &sum[1]);
            for(i = 2; i <= n; i++){
                scanf("%d", &x);
                sum[i] = sum[i-1] + x;/*记录前缀和*/
            }
            for(i = 1; i <= m; i++)
                scanf("%lld", &tmp[i]);
            ans = 0, pos = 0;
            for(i = 1; i <= m; i++){
                if(tmp[i]-ans > n-pos){
       /*判断下一次发呆前是否可以拾到全部石子*/
                    ans += n-pos;
                    pos = n;
                    break;
                }
                else {
                    int t = tmp[i]-1-ans;/*本次发呆前可以向前移动拾到的石子数量*/
                    pos += t;/*向前移动t单位*/
                    ans += t;/*时间经过t单位*/
                    ans += 1;/*发呆的单位时间*/
                    pos = Bin_pos(1, pos, sum[pos]-k);/*二分查找发呆后回到的位置*/
                }
                /*printf("%d %d\n", ans, pos);*/
            }
            if(pos < n)/*所有发呆结束但尚未拾到所有石子*/
                ans += n-pos;
            printf("%d\n", ans);
        }
        return 0;
    }
    int Bin_pos(int l, int r, int x){
        int mid;
        while(l <= r){
            mid = (l+r)/2;
            if(sum[mid] >= x)
                r = mid-1;
            else
                l = mid+1;
        }
        return max(0, l-1);
    }

[vjudge]: https://vjudge.net/contest/175275#problem/I