Worms-有解無憂

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 }

這題要注意的就是標簽式存盤的思路和注意超時問題，其他都不太難的

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244534.html

標籤：C++

上一篇：每日一課——【例外處理】c++標準例外處理：原理+方法

下一篇：C++面向物件：C++ 類 & 物件