鏈接：https://www.nowcoder.com/acm/contest/91/A
來源：牛客網(wǎng)

最近對抗生成網(wǎng)絡(luò)(GAN)很火，其中有一種變體WGAN，引入了一種新的距離來提高生成圖片的質(zhì)量。這個距離就是Wasserstein距離，又名鏟土距離。 這個問題可以描述如下:

有兩堆泥土，每一堆有n個位置，標號從1~n。第一堆泥土的第i個位置有a_i克泥土，第二堆泥土的第i個位置有b_i克泥土。小埃可以在第一堆泥土中任意移挪動泥土，具體地從第i個位置移動k克泥土到第j個位置，但是會消耗的體力。小埃的最終目的是通過在第一堆中挪動泥土，使得第一堆泥土最終的形態(tài)和第二堆相同，也就是a_i=b_i (1<=i<=n), 但是要求所花費的體力最小

左圖為第一堆泥土的初始形態(tài)，右圖為第二堆泥土的初始形態(tài)，顏色代表了一種可行的移動方案，使得第一堆泥土的形態(tài)變成第二堆泥土的形態(tài)

輸入描述:

輸入測試組數(shù)T，每組測試數(shù)據(jù),第一行輸入n，1<=n<=100000,緊接著輸入兩行，每行n個整數(shù)，

輸出描述:

對于每組數(shù)據(jù)，輸出一行，將a土堆的形態(tài)變成b土堆的形態(tài)所需要花費的最小體力

示例1

輸入

2 3 0 0 9 0 2 7 3 1 7 6 6 6 2

輸出

2 9

備注:

輸入數(shù)據(jù)量較大，建議使用scanf/printf

【分析】：想要代價最小，控制k*|i-j|最小的辦法是只移動相鄰的。那么只要保證k最小并且從左到右累加k（k必定為正數(shù)，因為k>0&&|i-j|>0,故abs（ a[i]-b[i] ）。

首先這里有一個簡化的思想。考慮到分好后所有的土堆數(shù)都等于bi，我們干脆以bi作為標準，讓所有的ai減去bi，如果是正數(shù)表明需要移走這個正數(shù)數(shù)量的土堆，注意負數(shù)需要移走的土堆數(shù)就是這個負數(shù)本身，下文中把處理過的牌組就叫做簡化后的土堆。

.可能會疑問那個差值可能是正可能是負（其實+/-可以看成移動的方向），這沒有關(guān)系，差值為正表示 i 移到 i+1，為負表示從 i+1 移到 i，其答案數(shù)都是加abs（ a[i]-b[i] ），所以可以等價。

貪心思想則是從左到右依次枚舉，將每個土堆上簡化后的數(shù)移動到右邊的土堆(再說一遍，是負數(shù)的就移走負數(shù))，這樣最后一組牌就自動變成bi了

但是如果簡化后的土堆中有bi怎么辦？第一個不為bi的土堆之前所有的土堆都不需要進行移動，否則步數(shù)偏大。但是在土堆中如果有bi，那沒有關(guān)系，因為他左邊的土堆一定會往他上面移動一定數(shù)量的土堆。

?【代碼】：

#include <bits/stdc++.h> using namespace std; const int maxn=1e5+100;int a[maxn],b[maxn]; int main() {int T;//cin>>T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);long long ans=0;for(int i=1;i<n;i++){ans += abs(a[i]-b[i]);//每次分配 答案+abs(a[i]-b[i])a[i+1] += a[i]-b[i];//a[i]-b[i]計算還差多少,后面的補上來，將該摞多余的土堆數(shù)放到下一摞 }printf("%lld\n",ans);}return 0; }

?【總結(jié)】：貪心選擇性:全局最優(yōu)解是由局部最優(yōu)解產(chǎn)生。貪心法比較容易實現(xiàn)，但是不好證明。移動負數(shù)個土堆也是不違反題意的，因為那相當于逆向移動了正數(shù)個土堆。問題的規(guī)模被一步步地縮小。

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/8848999.html

總結(jié)

以上是生活随笔為你收集整理的A Wasserstein Distance[贪心/模拟]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。