主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 J: Orz Problem B

问题 J: Orz Problem B

时间限制: 2 Sec  内存限制: 128 MB
提交: 22  解决: 6
[提交][状态][讨论版]

题目描述

  有n个村庄形成一个环形,每一个村庄与它左右两个村庄相连,其中1号村庄可以与n号村庄相连,n号村庄可以与1号村庄相连。
现在每个村庄一开始都有物资a[i]千克,但是由于每个地方的情况不同,所以每个村庄实际需要的物资为b[i]千克。
为了让每个村庄都能最终得到自己需要的物资重量,我们需要让物资在村庄之间转移,但是不可以从外界引入物资,
也就是物资的总数是一定的。
  现在物资可以在两个相邻的村庄之间转移,可是由于转移需要人力,所以它们想要让转移的资源总量最小,你能帮帮它们么?

输入

多组数据,处理到 没有数据 或者 n <= 0
每组数据的格式如下:
n             : 村庄数 (1 <= n <= 1,000,000)
a[1] ... a[n] : a[i]为i号村庄原有的资源数(0 <= a[i] <= 1,000,000,000);
b[1] ... b[n] : b[i]为i号村庄想要达到的资源数目(0 <= b[i] <= 1,000,000,000);

输出

输出一个结果,那就是最少花费,注意两个输出之间应有一个换行。
如果不可能做到,那么输出"No way"(没有引号)

样例输入

2
1 2
2 1
3
1 2 3
2 2 2
2
1 2
2 2

样例输出

1
1
No way

提示

[提交][状态][讨论版]