Codeforces 271 Div 2 B. Worms

题目链接：http://codeforces.com/contest/474/problem/B

解题报告：给你n个堆，第i个堆有ai个物品，物品的编号从1开始，第一堆的编号从1到a1，第二堆编号从a1+1到a1+a2.......，现在有m次查询，给你一个编号，让你求出这个编号的物品在第几个堆。

离线算法，先把m次查询按照编号从小到大排序，然后全部求出来之后按照输入的顺序排序就行了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int fan[1000005][2];
 7 
 8 struct node
 9 {
10     int d,cixu,ans;
11 }lab[100005];
12 bool cmpd(node a,node b)
13 {
14     return a.d < b.d;
15 }
16 bool cmpcixu(node a,node b)
17 {
18     return a.cixu < b.cixu;
19 }
20 int main()
21 {
22     int n,m;
23     while(scanf("%d",&n)!=EOF)
24     {
25         int d;
26         fan[0][1] = 0;
27         for(int i = 1;i <= n;++i)
28         {
29             scanf("%d",&d);
30             fan[i][0] = fan[i-1][1] + 1;
31             fan[i][1] = fan[i][0] + d - 1;
32         }
33         scanf("%d",&m);
34         for(int i = 0;i < m;++i)
35         {
36             scanf("%d",&lab[i].d);
37             lab[i].cixu = i;
38         }
39         sort(lab,lab+m,cmpd);
40         int f = 1;
41         for(int i = 0;i < m;++i)
42         {
43             while(1)
44             {
45                 if(lab[i].d >= fan[f][0] && lab[i].d <= fan[f][1])
46                 {
47                     lab[i].ans = f;
48                     break;
49                 }
50                 f++;
51             }
52         }
53         sort(lab,lab+m,cmpcixu);
54         for(int i = 0;i < m;++i)
55         printf("%d
",lab[i].ans);
56     }
57     return 0;
58 }            
59

View Code