[USACO 2009 Dec S]Music Notes
二分板子, 写的不太熟练 也可以直接使用upper_bound()
ac代码:
//寻找第一个大于前缀和的下标+1
//2(0 1) 3(2) 6(3 4 5)
#include <bits/stdc++.h>
using namespace std;
int num[50005];
int n ,q;
int found_first_bigger(int x)
{
int i = 0, j = n-1;
//1 2 2 3 4 5 6 7
int mid;
while(i<j)
{
mid = (i+j)/2;
if(num[mid]>x)//不是mid>x
{
j = mid;
}
else//mid<=x
{
i = mid+1;
}
}
return i;
}
int main()
{
cin>>n>>q;
cin>>num[0];
for(int i = 1; i<n; i++)
{
cin>>num[i];
num[i]+=num[i-1];
}
int temp;
for(int i = 0; i<q; i++)
{
cin>>temp;
cout<< found_first_bigger(temp) +1<<'\n';
//cout<< upper_bound(num , num+n, temp) - num +1<<'\n';
}
return 0;
}