首页 > 代码库 > Gergovia的酒交易B805(移动纸牌)

Gergovia的酒交易B805(移动纸牌)

 

试题描述

 直线上有 n 个等距的村庄,每个村庄要么买酒,要么卖酒。设第 i 个村庄对酒的需求为 ai (-1000<=ai<=1000),其中ai>0表示买酒,ai<0表示卖酒。所有村庄供需平衡,即所有 ai 之和等于0。把 k 个单位的酒从一个村庄运到相邻村庄需要 k 个单位的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在 64 位带符号整数的范围内。

输入
若干组数据,每组数据为两行。
对于每组数据,第一行有一个整数N,表示有N个酒窖,第二行有N个整数,从a1,a2一直到an。
输入的最后以0结尾。
输出
每组数据一行,每行一个整数,表示总费用。
输入示例
10
3 -1 -2 9 -4 -1 -7 9 -7 1
5
1000 -1000 1000 0 -1000
0
输出示例
33
3000
其他说明
数据范围:2 <= n <= 100 000
 

大概的思路:从最左边的往右推。因为线性村庄中最左边的酒一定要往右边运。所以,把当前走过的村庄的绝对值加起来,再加上当前村庄的(可以是负数),即为简单算法。具体见代码。

技术分享
 1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <algorithm> 7 using namespace std; 8 int a[1010101]; 9 int main()10 {11     int n;12     while(cin>>n)13     {14         if(n==0) break;15         for(int i=1;i<=n;i++) scanf("%d",&a[i]);16         int m=a[1],ans=0;17         for(int i=2;i<=n;i++)18         {19             ans+=abs(m);20             m+=a[i];21         }22         printf("%d\n",ans);23     }24     //system("pause");25     return 0;26 }
Gergovia的酒交易B805

 

Gergovia的酒交易B805(移动纸牌)