【uva 1442】Cav（算法效率）

题意：有一个由N个片段构成宽度的洞穴，已知洞顶 si 和洞底 pi 的高度，要求储存尽量多的燃料。

解法：O(n)，分别从1到N和从N到1扫一遍，调整每个片段合法的最大高度，求出答案。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 const int N=(int)1e6+10,D=1010;
 7 int n;
 8 int p[N],s[N],h[N];
 9 
10 int mmin(int x,int y) {return x<y?x:y;}
11 int main()
12 {
13     int T;
14     scanf("%d",&T);
15     while (T--)
16     {
17       scanf("%d",&n);
18       for (int i=1;i<=n;i++) scanf("%d",&p[i]);
19       for (int i=1;i<=n;i++) scanf("%d",&s[i]);
20       int t=s[1],sum=0;
21       for (int i=1;i<=n;i++)
22       {
23         if (t<p[i]) t=p[i];
24         if (t>s[i]) t=s[i];
25         h[i]=t;
26       }
27       t=s[n];
28       for (int i=n;i>=1;i--)
29       {
30         if (t<p[i]) t=p[i];
31         if (t>s[i]) t=s[i];
32         h[i]=mmin(h[i],t);
33         sum+=h[i]-p[i];
34       }
35       printf("%d
",sum);
36     }
37     return 0;
38 }