UVa 11054

　　题目大意：给一个整数序列，他们的和为0。通过对这些数进行移动，使得他们全部为0。在相邻两个数之间移动一个单位（如2，-1变成1，0）为一个单位的工作量，求最小的工作量。

　　用贪心解决，首先使第一个数为0，然后在考虑第二个数，以此类推。在把第一个数移为0的过程中，先考虑最近的需求或供给，此为贪心。

 1 #include <cstdio>
 2 #define MAXN 100000+10
 3 
 4 int a[MAXN];
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int n;
12     while (scanf("%d", &n) != EOF && n)
13     {
14         for (int i = 0; i < n; i++)
15             scanf("%d", &a[i]);
16         long long work = 0;
17         for (int i = 0; i < n; i++)
18         {
19             if (a[i] > 0)
20             {
21                 for (int j = i+1; j < n; j++)
22                     if (a[j] < 0)
23                     {
24                         int t = a[i];
25                         a[i] = a[j] = a[i] + a[j];
26                         if (a[j] > 0)   a[j] = 0;
27                         if (a[i] < 0)   a[i] = 0;
28                         work += (t - a[i]) * (j - i);
29                         if (a[i] == 0)   break;
30                     }
31             }
32             else if (a[i] < 0)
33             {
34                 for (int j = i+1; j < n; j++)
35                     if (a[j] > 0)
36                     {
37                         int t = a[i];
38                         a[i] = a[j] = a[i] + a[j];
39                         if (a[j] < 0)   a[j] = 0;
40                         if (a[i] > 0)   a[i] = 0;
41                         work += (a[i] - t) * (j - i);
42                         if (a[i] == 0)   break;
43                     }
44             }
45         }
46         printf("%lld
", work);
47     }
48     return 0;
49 }

View Code 1

　　这个是按照一点一点分析写的代码，不过用了2s多，后来把大于0和小于0的情况合并，如下：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define MAXN 100000+10
 4 
 5 int a[MAXN];
 6 
 7 int main()
 8 {
 9 #ifdef LOCAL
10     freopen("in", "r", stdin);
11 #endif
12     int n;
13     while (scanf("%d", &n) != EOF && n)
14     {
15         for (int i = 0; i < n; i++)
16             scanf("%d", &a[i]);
17         long long work = 0;
18         for (int i = 0; i < n; i++)
19             if (a[i])
20             {
21                 for (int j = i+1; j < n; j++)
22                     if (a[i]*a[j] < 0)
23                     {
24                         int t = a[i];
25                         a[i] = a[j] = a[i] + a[j];
26                         if (t*a[j] > 0)   a[j] = 0;
27                         if (t*a[i] < 0)   a[i] = 0;
28                         work += abs(t - a[i]) * (j - i);
29                         if (a[i] == 0)   break;
30                     }
31             }
32         printf("%lld
", work);
33     }
34     return 0;
35 }

View Code 2

　　可是超时了。。。后来在World of Seven 上看到这样一段描述：

“This is a greedy problem.
The problem is actually an array containing different numbers representing the wine.
The positive and negative means the demand and supply.
So we can greedily make it linear. That is make the first house 0. transport the supply or demand to the second.
And then, to the third.....At the same time, record down the moves required.
The greedy works because every move of the wine can be broken into the move between two consecutive houses.”

从宏观上进行考虑，而不管到底是给了谁。感觉有点眉目，但理解的不是很清楚，将供给或需求进行转移，根本就没往这方面想。。。下面是看网上的代码改的：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define MAXN 100000+10
 4 
 5 int a[MAXN];
 6 
 7 int main()
 8 {
 9 #ifdef LOCAL
10     freopen("in", "r", stdin);
11 #endif
12     int n;
13     while (scanf("%d", &n) != EOF && n)
14     {
15         for (int i = 0; i < n; i++)
16             scanf("%d", &a[i]);
17         long long work = 0;
18         for (int i = 0; i < n-1; i++)
19         {
20             a[i+1] += a[i];
21             work += abs(a[i]);
22         }
23         printf("%lld
", work);
24     }
25     return 0;
26 }

View Code 3