水题,记录一下low_bound(*begin,*end,num),其中low-bound是指以num为下界,寻找第一个比num大或相等的元素的指针,通过减去*begin指针我们可以获得相应的下标。
upper_bound( first, last, & val)算法返回一个非递减序列[first, last)中第一个 大于 val的地址。
lower_bound( first, last, & val)算法返回一个非递减序列[first, last)中第一个 大于等于 值val的地址。
区别好像就是lower_bound会返回等于的值,但是upper_bound是严格大于。
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll n,m,a[maxn],b[maxn],sum[maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=m;i++)cin>>b[i];
for(int i=1;i<=m;i++){
//ll index=upper_bound(sum,sum+n+1,b[i])-sum;
ll index=lower_bound(sum,sum+n+1,b[i])-sum;
cout<<index<<" "<<b[i]-sum[index-1]<<endl;
}
}