首页 > 其他 > 详细

CF978C Letters【前缀和+二分查找/几房几号】

时间:2018-06-02 10:31:17      阅读:395      评论:0      收藏:0      [点我收藏+]

【链接】:CF978C
【分析】:在前缀和数组种二分找到>=询问数的位置,根据位置就好操作了
【代码】:

#include<bits/stdc++.h>
using namespace std;
const int  INF =  0x3f3f3f3f;
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a); i<=(b); i++)
const int N = 2*1e5+5;
ll a[N],b[N],sum[N];
int main()
{
    int n,m;
    cin>>n>>m;
    memset(sum,0,sizeof(sum));
    rep(i,1,n) cin>>a[i], sum[i]=sum[i-1]+a[i];
    rep(i,1,m) cin>>b[i];
    rep(i,1,m)
    {
        if(b[i]<=a[1])
            printf("%d %lld\n",1,b[i]);
        else
        {
            ll j = lower_bound(sum,sum+n,b[i])-sum;
            printf("%lld %lld\n",j,b[i]-sum[j-1]);
        }
    }
}

CF978C Letters【前缀和+二分查找/几房几号】

原文:https://www.cnblogs.com/Roni-i/p/9124237.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!