音樂節拍
Description
FJ準備教他的奶牛彈奏一首歌曲，歌曲由N(1<=N<=50,000)種音節組成，編號為1到N，而且一定按照從1到N的順序進行彈奏，第i種音節持續B_i(1<=B_i<=10,000)個節拍，節拍從0開始計數，因此從節拍0到節拍B_1-1彈奏的是第1種音節，從B_1到B_1+B_2-1彈奏的是第2種音節，依此類推，
最近奶牛對彈琴不感興趣了，他們感覺太枯燥了，所以為了保持奶牛們注意力集中，FJ提出Q(1<=Q<=50,000)個問題，問題的格式都是“第T次節拍彈奏的是哪種音節”
每個問題對應一個T_i(0<=T_i<=節拍總數-1)請你幫奶牛來解決，
Input
第一行輸入兩個空格隔開的整數N和Q
第2至N+1行每行包含一個整數 B_i
第N+2-N+Q_1行每行包含一個整數T_i
Output
輸出有Q行，每行輸出對應問題的答案，
Sample Input
3 5
2
1
3
2
3
4
0
1
Sample Output
2
3
3
1
1
反思&題解
比賽&正解思路： 求出每個節拍的區間，之后將詢問排一下序，列舉區間判斷輸出就行了（二分會更快，比賽的時候第一個想到的就是二分，結果調了挺久沒調出來我太弱了QAQ ）
反思： 普及T2難度的題目，不切還有臉見人？？？
CODE
#include<bits/stdc++.h>
using namespace std;
struct arr
{
int x,num;
}t[50005];
int n,q,jp[50005][2],b[50005],ans[50005];
bool cmp(arr u,arr v)
{
return u.x<v.x;
}
int main()
{
freopen("mnotes.in","r",stdin);
freopen("mnotes.out","w",stdout);
scanf("%d%d",&n,&q);
int i;
jp[0][1]=-1;
for (i=1;i<=n;i++)
{
scanf("%d",&b[i]);
jp[i][0]=jp[i-1][1]+1;
jp[i][1]=jp[i][0]-1+b[i];
}
for (i=1;i<=q;i++)
{
scanf("%d",&t[i].x);
t[i].num=i;
}
sort(t+1,t+1+q,cmp);
int j=1;
for (i=1;i<=n;i++)
{
while (t[j].x>=jp[i][0] && t[j].x<=jp[i][1])
{
ans[t[j].num]=i;
j++;
if (j>q) break;
}
if (j>q) break;
}
for (i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/89491.html
標籤：區塊鏈