「BZOJ3412」[Usaco2009 Dec] Music Notes乐谱
Description
Input
第1行:两个整数N,Q.
第2到N+1行:第i+l行只有一个整数Bi.
第N+2到N+Q+I行:第N+i+l行只有一个整数Ti.
Output
第1到Q行:对与每个询问,在词问的时间内,奶牛敲击的是哪个音阶?
Sample Input
3 5
2
1
3
2
3
4
0
1
Sample Output
2
3
3
1
1
题解
二分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,q; int a[50005]; int main() { n=read();q=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) a[i]+=a[i-1]; for(int i=1;i<=q;i++) { int x=read(); x=upper_bound(a+1,a+n+1,x)-a; printf("%d\n",x); } return 0; } |
Subscribe