Letters CodeForces - 978C （二分）

Letters CodeForces - 978C

题意：n个寝室，每个寝室多个房间（1-a[i]）,一共m封信只知道房间号，现在要求把信送到第几个寝室的第几个房间里去，房间号从第一个寝室到第n个寝室的第一个房间到最后一个房间排下去

题意：用个二分查找吧，省点时间，二分才658ms，爆搜1600多ms

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn=;

int main()

{

    long long int n,m;

    cin>>n>>m;

    long long int sum[maxn]={};

    long long int a[maxn];

    for(long long int i=;i<=n;i++)

    {

        cin>>a[i];

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

    }

    while(m--)

    {

        int flag;

        long long  int t;

        scanf("%lld",&t);

        long long int l=,r=n;

        while(r-l>)

        {

            long long int mid=(l+r)/;

            if(sum[mid]>t)

                r=mid;

            else

                l=mid;

        }

            if(t-sum[l]==)

                printf("%lld %lld\n",l,a[l]);

                else printf("%lld %lld\n",l+,t-sum[l]);

    }

}

int l = ,r = n;

        while(r > l) {

            int mid = (l + r + ) >> ;

            if(... > ...)

                r = mid - ;

            else

                l = mid;

        }

巴特西

Letters CodeForces - 978C （二分）

最新文章

热门文章