Codeforces 278B Books

好久没有写二分了

题意：有n本书每本书有一个阅读时间ai 要在t时间内读最多的书读书的顺序是连续的，如果无法读完一本书就不能开始

最开始觉得会是个dp,但是动规方程写不出来。想想会不会是二分呢，也写不出来

看了题解发现，输入的时候要做一个巧妙的处理

因为书是连续读的，如果ai存的是第1 到第i本书所用的时间总和的话，那读【i，j】本书的时间就是ai-aj，这样就不需要循环算了啊！

于是固定一个起点二分找终点

太久没写二分的结果就是居然连二分的条件都不会了。

#include<stdio.h>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#define inf 1000000000

using namespace std;

int n, t;

int a[100005];

//int dp[100005];

int main()

{

    while(scanf("%d%d",&n,&t) != EOF){

        a[0] = 0;

        for(int i = 1; i <= n; i++){

            scanf("%d",&a[i]);

            a[i] += a[i - 1];

        }

        //memset(dp,0,sizeof(dp));

        int cnt = 0;

        for(int i = 0; i < n; i++){

            int left = i + 1;

            int right = n;

            int mid = (left + right) / 2;

            while(left <= right){

                if(a[mid] - a[i] > t){

                    right = mid - 1;

                }

                else{

                    left = mid + 1;

                }

                mid = (left + right) / 2;

            }

            cnt = max(cnt, left - i);

        }

        printf("%d\n",cnt - 1);

    }

    return 0;

}

这个区间左右都是闭的，a0 是用来辅助的所以最后答案是cnt - 1

巴特西

Codeforces 278B Books

最新文章

热门文章