474B Worms

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole n ordered piles of worms such that i-th pile contains ai worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to a1, worms in second pile are labeled with numbers a1 + 1 to a1 + a2 and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.

Input

The first line contains a single integer n (1 ≤ n ≤ 105), the number of piles.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 103, a1 + a2 + ... + an ≤ 106), where ai is the number of worms in the i-th pile.

The third line contains single integer m (1 ≤ m ≤ 105), the number of juicy worms said by Marmot.

The fourth line contains m integers q1, q2, ..., qm (1 ≤ qi ≤ a1 + a2 + ... + an), the labels of the juicy worms.

Output

Print m lines to the standard output. The i-th line should contain an integer, representing the number of the pile where the worm labeled with the number qi is.

 

 

题意分析：输入n意为有n堆虫，之后的第二行各个数字为每堆的虫的数量，第三行为要搜索的虫子的个数，最后一行一次是各个要找的虫子的位序。我们要求的是每个要找的虫子分别在第几堆里面。

算法思路：这是一个一个简单的标签式存储和搜索的题目，利用两个数组，一个用来存所有虫子的位置，另外一个数组用来存对应虫子的组别，直接输出即可。

需要注意的是，输入和分组的操作要同步执行，不能在下面查找的过程中去搜索全部，不然会超时。

下面出示超时代码：

 1 #include<iostream>
 2 using namespace std;
 3 int n, a[100000], m, b[100000], sum[100000];//n代表堆的数目，a[]存储每堆中虫的数目，m表示上等虫的个数，b[]存储每个上等虫的位置
 4 int main()
 5 {
 6     cin >> n;
 7     for (int i = 0;i < n;i++)
 8     {
 9         cin >> a[i];
10         if (i == 0)sum[i] = a[i];
11         else sum[i] = a[i] + sum[i - 1];
12     }
13     cin >> m;
14     for (int i = 0;i < m;i++)
15     {
16         cin >> b[i];
17     }
18     for (int i = 0;i < m;i++)
19     {
20         for (int j = 0;j < n-1;j++)
21         {
22             if (b[i] <=sum[0])
23             {
24                 cout << 1 << endl;
25                 break;
26             }
27             else if(b[i] > sum[j] && b[i]<=sum[j + 1])
28             {
29                 cout << j + 2<<endl;
30                 break;
31             }
32         }
33     }
34     return 0;
35 }

 

显然可见： 在输入之后每一个虫子的搜索都从头开始的行为是一定会超时的。下面出示ac代码：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n, m;
 5 int a[100010], ans[1000010];
 6 
 7 int main() {
 8     cin >> n;
 9     for (int i = 1; i <= n; i++) {
10         cin >> a[i];
11         a[i] += a[i - 1];
12 
13         for (int j = a[i - 1] + 1; j <= a[i]; j++)
14             ans[j] = i;
15     }
16     cin >> m;
17     for (int i = 1; i <= m; i++) {
18         int tmp;
19 
20         cin >> tmp;
21         cout << ans[tmp] << endl;
22     }
23 }

这题要注意的就是标签式存储的思路和注意超时问题，其他都不太难的