BestCoder Round #34_1002 以及 hdu 5191

枚举最终的W堆积木在哪，确定了区间，那么就需要把高于H的拿走，低于H的补上，高处的积木放到矮的上面，这样最优。

注意多出来的积木可以放在已有积木的前面或者后面，独立成一堆积木，所以需要在n堆积木的前后分别开一个长度为w的数组，所以整个数组的长度应该为n+2*w.

代码如下：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 long long int a[150010],high[150010],low[150010];     //high数组用来保存前i个元素中比h高的部分的总和，low组用来保存前i个元素中比h低的部分的总和
 5 
 6 int main()
 7 {
 8     int n,w,h;
 9 
10     while(scanf("%d%d%d",&n,&w,&h)!=EOF)
11     {
12         long long int sum=0;
13         memset(a,0,sizeof(a));
14         memset(high,0,sizeof(high));
15         low[0]=0;                          //注意初始化
16         for(int i=1;i<=w;i++)
17             low[i]=i*h;
18         for(int i=w+1;i<=w+n;i++)
19         {
20             scanf("%I64d",&a[i]);
21             sum+=a[i];
22             if(a[i]>h)                     //分类
23             {
24                 high[i]=high[i-1]+a[i]-h;
25                 low[i]=low[i-1];
26             }
27             else
28             {
29                 low[i]=low[i-1]+h-a[i];
30                 high[i]=high[i-1];
31             }
32         }
33         for(int i=w+n+1;i<=n+w+w;i++)
34         {
35             high[i]=high[i-1];
36             low[i]=low[i-1]+h;
37         }
38         if(sum<(long long int)w*h)
39         {
40             printf("-1
");
41             continue;
42         }
43         long long int step=999999999999;
44         for(int i=1;i<=n+w+1;i++)
45         {
46             if(high[i+w-1]-high[i-1]==low[i+w-1]-low[i-1])
47             {
48                 if(step>high[i+w-1]-high[i-1])
49                     step=high[i+w-1]-high[i-1];
50             }
51             if(high[i+w-1]-high[i-1]>low[i+w-1]-low[i-1])
52             {
53                 if(step>high[i+w-1]-high[i-1])
54                     step=high[i+w-1]-high[i-1];
55             }
56             if(high[i+w-1]-high[i-1]<low[i+w-1]-low[i-1])
57             {
58                 if(step>low[i+w-1]-low[i-1])
59                     step=low[i+w-1]-low[i-1];
60             }
61         }
62         printf("%I64d
",step);
63     }
64     return 0;
65 }