Wasserstein Distance

最近对抗生成网络(GAN)很火，其中有一种变体WGAN，引入了一种新的距离来提高生成图片的质量。这个距离就是Wasserstein距离，又名铲土距离。

这个问题可以描述如下:

有两堆泥土，每一堆有n个位置，标号从1~n。第一堆泥土的第i个位置有a_i克泥土，第二堆泥土的第i个位置有b_i克泥土。小埃可以在第一堆泥土中任意移挪动泥土，具体地从第i个位置移动k克泥土到第j个位置，但是会消耗 $k\cdot\left| i-j \right|$ 的体力。小埃的最终目的是通过在第一堆中挪动泥土，使得第一堆泥土最终的形态和第二堆相同，也就是a_i=b_i (1<=i<=n), 但是要求所花费的体力最小

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

输入测试组数T，每组测试数据,第一行输入n，1<=n<=100000,紧接着输入两行，每行n个整数，前一行为a₁, a₂,…,a_n,后一行为b₁,b₂,…,b_n.其中0<=a_i,b_i<=100000,1<=i<=n,数据保证 $\sum_{i=1}^{n}{a_{i}}=\sum_{i=1}^{n}{b_{i}}$

#include <cstdio> const int mn=1e5+5; int a[mn],b[mn]; int main(){ int n,T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); long long o=0,x=0; for(int i=1;i<=n;i++){ scanf("%d",&b[i]); x+=a[i]-b[i]; if(x>0) o+=x; else o-=x; } printf("%lld\n",o); } return 0; }

rd = lambda: map(int, input().split()) t = int(input()) for _ in range(t): n = int(input()) d, r = 0, 0 a, b = rd(), rd() for i in range(n): d += next(a) - next(b) r += abs(d) print(r)

详情