CodeForces 567B Berland National Library hdu-5477 A Sweet Journey

　　这类题一个操作增加多少，一个操作减少多少，求最少刚开始为多少，在中途不会出现负值，模拟一遍，用一个数记下最大的即可

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 const int HASH=57;
 5 
 6 int n,num[110],head[HASH],next[110];
 7 
 8 void insert(int s)
 9 {
10     int h=num[s]%HASH;
11     int u=head[h];
12     while(u) u=next[u];
13     next[s]=head[h];//原来的链表头成为s的next
14     head[h]=s;//s成为head[h]的链表头
15 }
16 
17 int erase(int s)
18 {
19     int h=num[s]%HASH;
20     int u=head[h];
21     while(u)
22     {
23         if(num[u]==num[s])
24         {
25             num[u]=0;
26             return 1;
27         }
28         u=next[u];
29     }
30     return 0;
31 }
32 
33 int main()
34 {
35     while(scanf("%d",&n)==1)
36     {
37         int x,cap=0,j=1,maxcap=0;
38         char op[2];
39         memset(head,0,sizeof(head));
40         for(int i=1;i<=n;i++)
41         {
42             scanf("%s%d",op,&num[j]);
43             if(op[0]=='+')
44             {
45                 insert(j);
46                 j++;
47                 cap++;
48                 //printf("cap=%d
",cap);
49                 if(cap>maxcap) maxcap=cap;
50             }
51             else
52             {
53                 if(erase(j)) cap--;
54                 else maxcap++;//在记下maxcap之前已经在里面
55                 //printf("cap=%d
",cap);
56                 if(cap>maxcap) maxcap=cap;
57             }
58         }
59         printf("%d
",maxcap);
60     }
61     return 0;
62 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 int T,n,a,b,L,cas=1;
 5 
 6 int main()
 7 {
 8     scanf("%d",&T);
 9     while(T--)
10     {
11         scanf("%d%d%d%d",&n,&a,&b,&L);
12         int l,r,strength=0,min=0,last=0;
13         for(int i=0;i<n;i++)
14         {
15             scanf("%d%d",&l,&r);
16             strength+=b*(l-last)-a*(r-l);
17             if(strength<min) min=strength;
18             last=r;
19         }
20         printf("Case #%d: %d
",cas++,-min);    
21     }
22     return 0;
23 }

View Code