英文题面:
De Prezer loves movies and series. He has watched theTroy for like 100 times and also he is a big fan ofSupernatural series.So, he did some researches and found a cursed object which hadn lights on it and initially all of them were turned off.Because of his love to theTroy, he called that object Troy.
He looked and saw a note on it in Khikulish (language of people of Khikuland): "Ma in hame rah umadim, hala migi … ? … Mage man De Prezer am k mikhay mano … ? …. Man se sale … To boro …. beshur manam miram … o mishuram".
He doesn’t know Khikulish, so just ignored the note and tested theTroy.
He realized that the light number i stays turned on for exactly ai seconds, and then it turns itself off (if it is turned on, in timet, in time t+ai-1 it will be turned on, but on timet+ai it won’t be) and the next light will be turned on (ifi<n, next light is the light numberi+1, otherwise it is light with number 1).
For example if n=2 and we turn on the first light in time0, it will be turned on in hole interval [0,a1) and in hole interval [a1,a1+a2) the second light will be turned on and so on.
In time 0 he turns on the light number1.
De Prezer also loves query.So he gives you q queries.In each query he will give you integer t (the time a revengeful ghost attacked him) and you should print the number of the light that is turned on, in timet.
Input
The first line of input contains two integers n and q.
The second line contains n space separated integers,a1,a2,…,an .
The next q lines, each line contains a single integert .
1≤n,q≤105
1≤ai≤109
1≤t≤1018
Output
For each query, print the answer in one line.
就是说有n盏灯,然后给出每盏灯亮的时间(第一盏从时刻0开始亮直到时刻0+a1-1,,第二盏在a1时刻亮起,以此类推),然后题目给出q组询问,询问内容是一个t,要你给出t时刻亮的时哪盏灯。我的做法是每次询问就来一次二分查找,log2n的复杂度再盛上10^5次询问可以接受。
Sample test(s):
Input
5 71 2 3 4 51237141516
Output
2234512
这组测试数据还是业界良心的,爆出了可能出错的坑,这一串灯是循环的首尾相接地亮,所以那个t是10^18这么大,要取模。
代码:
#include <iostream>#include<stdio.h>using namespace std;long long int start[100005];//每盏灯开始亮时刻long long int End[100005];//每盏灯亮完时刻int n,q,a;long long int t;int work(long long int ask)//每次二分查找函数{int p=1;int p1=1;int p2=n;while(ask<start[p]||ask>End[p]){p=(p1+p2)/2;if(ask>=start[p]&&ask<=End[p]){break;}else if(ask>=start[p1]&&ask<=End[p1]){p=p1;break;}else if(ask>=start[p2]&&ask<=End[p2]){p=p2;break;}else if(ask<start[p]&&ask>End[p1]){p2=p;}else if(ask>End[p]&&ask<start[p2]){p1=p;}}return p;//p就是那盏灯}int main(){scanf("%d%d",&n,&q);start[1]=0;for(int i=1;i<=n;i++){scanf("%d",&a);End[i]=start[i]+a-1;start[i+1]=start[i]+a;}while(q–){scanf("%I64d",&t);printf("%d\n",work(t%start[n+1]));}return 0;}
伟人所达到并保持着的高处,并不是一飞就到的,