HDOJ 4302 Holedox Eating (multiset || 线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4302

思路：很多人说这题是个线段树题。。。不过当时没想出来怎么用线段树做~后面再补吧。。。

比赛时用的方法就是用multiset模拟，中间WA好几次打了几个补丁才过的（果然我好弱）。。。有一个错是走数据才看出来的，就是当当前位置比set里的所有元素都要大时，lower_bound()找不到合适的元素会返回end()的迭代器，这种情况需要特殊处理一下。

附个数据吧~

HDOJ 4302 数据

50

6 16
1
0 0
0 2
0 1
1
0 3
0 1
1
0 0
1
1
1
0 5
0 2
1
1



27 9
1
1
0 21
0 16
1
1
0 0
1
0 13



1 24
1
1
1
0 0
1
1
0 0
1
1
0 0
1
0 0
1
0 0
1
0 0
1
1
1
1
1
0 0
1
0 0



16 11
1
0 11
0 8
1
0 3
1
0 12
0 15
0 11
0 7
0 11



1 10
0 0
0 0
1
1
1
0 0
0 0
0 0
1
1



30 22
0 21
0 11
1
0 14
0 2
0 27
0 1
1
1
1
0 1
0 25
0 0
1
0 26
0 20
1
0 20
0 8
1
1
1



11 19
0 3
0 6
0 7
1
1
0 5
1
1
1
0 8
0 3
1
0 6
0 9
1
1
0 1
0 10
0 2



3 26
0 0
0 2
1
0 0
0 0
1
1
0 1
0 0
1
0 0
0 1
0 2
1
1
1
0 2
1
0 2
0 1
0 1
1
1
1
1
1



16 1
1



14 7
1
0 8
1
1
1
1
0 6



1 21
0 0
0 0
0 0
1
1
1
1
0 0
1
0 0
1
0 0
1
0 0
0 0
0 0
1
0 0
0 0
1
1



17 20
0 0
1
1
0 15
1
1
1
0 2
0 13
0 4
0 2
0 6
1
1
0 14
0 14
1
1
0 12
0 13



18 2
0 12
0 13



10 3
1
1
0 8



14 27
1
0 7
1
1
1
0 2
0 7
1
0 13
1
0 6
0 11
1
0 1
1
0 1
1
1
1
1
1
1
1
1
1
1
1



14 26
0 13
1
0 6
0 8
1
0 0
1
0 3
0 2
1
1
1
0 1
1
0 8
0 4
0 12
1
0 6
1
0 10
1
0 11
1
0 13
0 12



22 11
0 6
0 15
1
1
1
0 2
1
0 7
1
1
0 21



3 11
0 2
1
0 0
0 0
0 0
1
1
1
0 2
1
1



29 24
0 13
1
1
1
1
1
0 3
1
0 7
1
0 27
1
0 11
1
1
1
1
1
1
0 28
1
0 24
0 5
1



20 0



8 22
1
1
1
1
1
1
0 1
0 3
0 2
1
1
0 3
0 0
1
0 5
1
1
1
0 3
1
0 7
1



11 2
1
1



21 10
1
1
0 17
0 6
0 2
1
1
0 7
1
1



7 14
1
0 1
1
0 2
1
1
1
1
1
1
1
1
1
0 0



21 28
0 13
1
0 7
0 19
1
1
1
0 14
1
0 6
0 14
1
0 20
0 18
0 11
1
0 7
1
0 9
1
0 19
1
0 12
0 20
1
1
1
1



18 18
0 3
0 9
0 10
0 13
0 14
0 1
1
0 11
0 10
1
0 14
1
0 16
0 12
1
0 3
0 2
1



9 23
0 4
0 5
1
0 1
0 0
0 7
1
1
1
1
0 7
0 8
0 8
1
0 0
1
1
1
0 0
1
1
0 3
1



4 1
1



30 4
0 6
1
0 29
0 18



25 24
1
0 1
0 13
0 4
0 1
1
0 11
0 19
1
0 9
1
1
0 1
0 4
0 23
0 8
0 6
1
1
1
0 14
1
1
1



23 18
0 4
1
0 1
0 16
0 7
1
1
0 8
0 4
0 5
1
1
0 4
1
0 22
0 20
0 14
1



29 25
1
1
0 13
0 18
1
1
0 20
1
0 20
0 7
1
1
1
0 16
0 21
1
0 7
0 25
1
1
0 24
0 19
1
0 1
0 9



8 10
0 1
1
1
0 2
1
0 1
0 7
0 1
0 3
0 6



11 19
0 8
1
1
0 5
0 6
1
0 0
0 4
0 4
0 9
1
1
1
1
0 1
0 10
1
1
1



21 2
1
0 6



24 27
1
1
0 11
1
0 0
0 14
0 4
0 14
0 18
1
1
1
0 0
0 9
0 12
0 19
1
0 16
0 6
0 10
0 13
1
0 16
0 4
0 2
1
0 10



9 29
1
0 5
1
0 0
0 1
0 8
1
0 4
0 1
0 3
1
0 0
0 4
0 8
0 7
0 4
1
1
0 0
0 0
1
1
1
0 6
0 4
1
1
0 4
0 6



18 15
1
1
0 10
0 10
1
1
0 14
0 16
0 17
0 1
1
1
0 15
1
0 12



17 11
0 5
0 7
1
0 0
1
0 11
0 8
1
1
1
1



13 24
1
0 8
0 0
0 11
1
1
0 10
0 3
0 4
1
0 9
0 5
1
1
0 5
0 8
1
1
0 11
0 7
0 11
1
0 5
0 9



23 25
1
0 3
1
1
0 6
0 13
1
1
0 9
1
1
0 8
1
0 18
1
0 15
0 0
0 10
0 21
0 17
1
0 13
1
1
0 3



9 1
0 3



8 0



20 1
1



1 13
0 0
0 0
0 0
1
1
0 0
1
1
1
0 0
0 0
0 0
0 0



11 6
0 5
1
1
1
1
0 10



16 6
1
1
1
0 1
1
1



3 12
1
1
0 0
0 2
0 2
0 0
1
0 0
0 0
1
0 0
0 2



29 20
0 11
1
1
1
0 28
0 2
1
0 7
0 23
1
0 28
0 23
1
1
0 8
0 12
0 27
0 17
1
0 28



27 1
0 26


输出：

Case 1: 6
Case 2: 42
Case 3: 0
Case 4: 11
Case 5: 0
Case 6: 48
Case 7: 16
Case 8: 3
Case 9: 0
Case 10: 8
Case 11: 0
Case 12: 28
Case 13: 0
Case 14: 0
Case 15: 35
Case 16: 36
Case 17: 33
Case 18: 6
Case 19: 84
Case 20: 0
Case 21: 17
Case 22: 0
Case 23: 17
Case 24: 2
Case 25: 60
Case 26: 10
Case 27: 33
Case 28: 0
Case 29: 6
Case 30: 29
Case 31: 22
Case 32: 52
Case 33: 2
Case 34: 26
Case 35: 0
Case 36: 22
Case 37: 16
Case 38: 17
Case 39: 22
Case 40: 17
Case 41: 33
Case 42: 0
Case 43: 0
Case 44: 0
Case 45: 0
Case 46: 5
Case 47: 1
Case 48: 0
Case 49: 45
Case 50: 0

multiset 解法（打了好多补丁，好丑。。。）

6771936

2012-09-15 16:45:47

Accepted

4302

171MS

280K

2665 B

C++

AbandonZHANG

View Code

线段树解法（用线段树求[0,now]区间最大数，求[now,l]区间最小的数）

6774072

2012-09-15 22:13:02

Accepted

4302

296MS

1808K

3792 B

C++

AbandonZHANG

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <iomanip>
  6 #include <climits>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include <set>
 11 #include <map>
 12 #include <algorithm>
 13 #include <string>
 14 #include <cstring>
 15 #define MID(x,y) ( ( x + y ) >> 1 )
 16 #define FOR(i,s,t) for(int i=s; i<t; i++)
 17 
 18 using namespace std;
 19 
 20 typedef long long LL;
 21 
 22 const int N=100005;
 23 int M;
 24 int sum[N<<2];
 25 
 26 void PushUp(int rt)
 27 {
 28     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 29 }
 30 
 31 void BuildTree(int n)
 32 {
 33     for (M=1;M<=n+2;M<<=1);
 34     for (int i=1;i<N<<2;i++)
 35         sum[i]=0;
 36 }
 37 
 38 void Update(int n,int v)
 39 {
 40     for (sum[n+=M]+=v,n>>=1;n;n>>=1)
 41         PushUp(n);
 42 }
 43 
 44 int Qsum(int s,int t,int l,int r,int rt)
 45 {
 46     if (s<=l && r<=t)
 47     {
 48         return sum[rt];
 49     }
 50 
 51     int mid=MID(l,r);
 52     int ans=0;
 53     if (s<=mid) ans+=Qsum(s,t,l,mid,rt<<1);
 54     if (mid<t)  ans+=Qsum(s,t,mid+1,r,rt<<1|1);
 55     return ans;
 56 }
 57 
 58 int Querymax(int s,int l,int r,int rt)
 59 {
 60     if (l==r)
 61     {
 62         return l;
 63     }
 64 
 65     int mid=MID(l,r);
 66     if (sum[rt<<1]>=s)
 67     {
 68         return Querymax(s,l,mid,rt<<1);
 69     }
 70     else return Querymax(s-sum[rt<<1],mid+1,r,rt<<1|1);
 71 }
 72 
 73 int Querymin(int s,int l,int r,int rt)
 74 {
 75     if (l==r)
 76     {
 77         return l;
 78     }
 79 
 80     int mid=MID(l,r);
 81     if (sum[rt<<1|1]>=s)
 82     {
 83         return Querymin(s,mid+1,r,rt<<1|1);
 84     }
 85     else return Querymin(s-sum[rt<<1|1],l,mid,rt<<1);
 86 }
 87 
 88 int main()
 89 {
 90     //freopen("test.in","r+",stdin);
 91 
 92     int t,caseo=1;
 93     scanf("%d",&t);
 94     while(t--)
 95     {
 96         printf("Case %d: ",caseo++);
 97         int ans=0;
 98         int l,n;
 99         scanf("%d%d",&l,&n);
100         BuildTree(l);
101         int h=0;
102         int dir=0;
103         for (int i=0;i<n;i++)
104         {
105             int p;
106             scanf("%d",&p);
107             if (p==0)
108             {
109                 int num;
110                 scanf("%d",&num);
111                 Update(num,1);
112             }
113             else
114             {
115                 if (sum[1]==0)  continue;
116                 int a1=Qsum(0,h,0,M-1,1);
117                 int a2=Qsum(h,M,0,M-1,1);
118                 if (a1==0)
119                 {
120                     int b2=Querymin(a2,0,M-1,1);
121                     dir=1;
122                     ans+=b2-h;
123                     h=b2;
124                     Update(b2,-1);
125                 }
126                 else if (a2==0)
127                 {
128                     int b1=Querymax(a1,0,M-1,1);
129                     dir=-1;
130                     ans+=h-b1;
131                     h=b1;
132                     Update(b1,-1);
133                 }
134                 else
135                 {
136                     int b1=Querymax(a1,0,M-1,1);
137                     int b2=Querymin(a2,0,M-1,1);
138                     if (b2-h>h-b1)
139                     {
140                         ans+=h-b1;
141                         h=b1;
142                         dir=-1;
143                         Update(b1,-1);
144                     }
145                     else if (b2-h<h-b1)
146                     {
147                         ans+=b2-h;
148                         h=b2;
149                         dir=1;
150                         Update(b2,-1);
151                     }
152                     else
153                     {
154                         ans+=b2-h;
155                         if (dir==1)
156                         {
157                             h=b2;
158                             Update(b2,-1);
159                         }
160                         else
161                         {
162                             h=b1;
163                             Update(b1,-1);
164                         }
165                     }
166                 }
167             }
168         }
169         printf("%d\n",ans);
170     }
171     return 0;
172 }

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG