ACM 扫描法 Wine trading in Gergovia

本文主要是介绍ACM 扫描法 Wine trading in Gergovia，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

滴，集训第七天打卡。

今天是紫书第八章训练，是高效算法设计..

就是不用奇技淫巧都会超时...

这里贴一题扫描法。

UVA 11054 Wine trading in Gergovia

题目大意：直线上有n个等距的村庄，每个村庄要么买酒（ai>0），要么卖酒（ai<0）,所有村庄供需平衡，即所有ai之和等于0.把k个单位的酒从一个村庄运到相邻村庄需要k个单元的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求。

思路：用扫描法，从最左边的村庄开始。

#include <stdio.h>
#include <stdlib.h>
int main()
{int n,i;long long ans,a,last;while(scanf("%d",&n)){if(n==0)break;ans=last=0;for(i=0;i<n;i++)		{scanf("%lld",&a);ans+=abs(last);last+=a;}printf("%lld\n",ans);}
}

这篇关于ACM 扫描法 Wine trading in Gergovia的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---