Wasserstein Distance

发布时间: 2018年4月15日 22:23   最后更新: 2018年4月15日 22:23   时间限制: 1000ms   内存限制: 128M

最近对抗生成网络(GAN)很火,其中有一种变体WGAN,引入了一种新的距离来提高生成图片的质量。这个距离就是Wasserstein距离,又名铲土距离。这个问题可以描述如下:有两堆泥土,每一堆有$n$个位置,标号从$1~n$。第一堆泥土的第$i$个位置有$a_i$克泥土,第二堆泥土的第$i$个位置有$b_i$克泥土。小埃可以在第一堆泥土中任意移挪动泥土,具体地从第$i$个位置移动$k$克泥土到第$j$个位置,但是会消耗$k \times|i - j|$的体力。小埃的最终目的是通过在第一堆中挪动泥土,使得第一堆泥土最终的形态和第二堆相同,也就是$a_i=b_i$ ($1 \le i \le n$), 但是要求所花费的体力最小。

304389_1523177075706_10B9DAF51A50400E3D7599CB18323F6D.png

上图为第一堆泥土的初始形态,下图为第二堆泥土的初始形态,颜色代表了一种可行的移动方案,使得第一堆泥土的形态变成第二堆泥土的形态。

304389_1523177081049_11591BA5FB42D6166391FCBF18B3649B.png

你能帮帮小埃吗, 要不然他可能真的QwQ!

作为埃森哲公司的一员,你在解决问题的同时也向A 介绍了埃森哲公司的业务范围。为了全方位地满足客户的需求,正在不断拓展自身的业务服务网络,包括管理及信息技术咨询、企业经营外包、企业联盟和风险投资。除了以产品制造业、通信和高科技、金融服务、资源、政府机构等不同行业划分服务内容之外,还从以下几方面提供咨询服务:

  • 客户关系管理
  • 业务解决方案
  • 电子商务
  • 供应链管理

输入测试组数$T$,每组测试数据,第一行输入$n$,$1\le n \le 100000$,紧接着输入两行,每行n个整数,前一行为$a_1, a_2,…,a_n$,后一行为$b_1,b_2,…,b_n$.其中$0 \le a_i,b_i \le 100000$,$1 \le i \le n$,数据保证$$\sum_{i=1}^n a_i = \sum_{i=1}^n b_i$$

对于每组数据,输出一行,将a土堆的形态变成b土堆的形态所需要花费的最小体力

复制
2
3
0 0 9
0 2 7
3
1 7 6
6 6 2
2
9

输入数据量较大,建议使用scanf/printf

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛