鏈接：https://www.nowcoder.com/acm/contest/140/G

White Cloud placed n containers in sequence on a axes. The i-th container is located at x[i] and there are a[i] number of products in it.
White Rabbit wants to buy some products. The products which are required to be sold must be placed in the same container.
The cost of moving a product from container u to container v is 2*abs(x[u]-x[v]).
White Cloud wants to know the maximum number of products it can sell. The total cost can't exceed T.

輸入描述:

The first line of input contains 2 integers n and T(n <= 500000,T <= 1000000000000000000)
In the next line there are n increasing numbers in range [0,1000000000] denoting x[1..n]
In the next line there are n numbers in range[0,10000] denoting a[1..n]

輸出描述:

Print an integer denoting the answer.

示例1

輸入

2 3 1 2 2 3

輸出

4


https://www.nowcoder.com/discuss/88268?type=101&order=0&pos=2&page=0
https://blog.csdn.net/wookaikaiko/article/details/81177870
輸入：n T
　　　x[0].x[1],x[2]...
　　　a[0].a[1].a[2]...
題意：給出n個箱子，每個箱子里的產(chǎn)品個數(shù)a[i]不同， 我們把一個箱子里的物品移到另一個箱子里去需要2*abs（x[i]-x[j]）的花費，問在花費不超過T的前提下，可以移動到同一個位置的物品最多多少

思路：我們想到我們要盡量把其他的物品移到一個位置，我們先按數(shù)軸位置排一個序，然后我們有兩個問題
1.移到哪 ：我們肯定選取的是物品數(shù)中位數(shù)所在得箱子里，這個是顯而易見得
2.哪些移到那里　　 ：我們肯定是把與中位數(shù)相鄰的一些數(shù)移過來，因為其他位置更遠，顯然花費更大，劃不來，所以肯定是一個區(qū)間，我們找出那個區(qū)間的中位數(shù)

方法：我們實現(xiàn)的主要方法呢就是我們二分那個最多物品數(shù)，然后我們判斷用這個物品數(shù)是否能找到那個把其他數(shù)移到中位數(shù)的區(qū)間，如果找到，我們再嘗試更大的物品數(shù)，否則放小
找尋那個區(qū)間的方法：我們枚舉那個左端點，再枚舉長度，直到找到那個移到中位數(shù)花費不超過T的物品數(shù)
我們定義四個數(shù)組 prec prew sufc sufw
prew存的是前i個物品數(shù) 所以遞推式是 prew[i]=prew[i-1]+a[i];
prec存的是前i個移到當前位置的花費 所以遞推式是 prec[i]=prec[i-1]+prew[i-1]*(x[i]-x[i-1])
(因為prec[i]是把前i個物品移到當前的花費是多少，說明我們之前已經(jīng)把所有的物品移到了i-1位置，所以我們只要把所有物品數(shù)prew[i-1]*（i-1和i之間的相隔位置）)

sufw存的是i到n的物品數(shù)，兩個數(shù)組和上面的方法一樣，只是方向變了，所以不再做贅述

我們?nèi)绾吻蟆緇,r】的花費呢
prec[r]-prec[l-1]-prew[l-1]*(x[i]-x[l-1])
(因為prec[r]計算了1-l-1這一部分的物品從1移到r的花費，而prec[l-1]只有1-l-1這一段距離的花費，所以我們要格外的減去)

下面看代碼 #include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+10; struct node {ll x,w; }a[N]; using namespace std; ll n,T; ll prew[N],prec[N],sufw[N],sufc[N]; ll cal_pre(ll l,ll r) {return prec[r]-prec[l-1]-prew[l-1]*(a[r].x-a[l-1].x); } ll cal_suf(ll l,ll r) {return sufc[l]-sufc[r+1]-sufw[r+1]*(a[r+1].x-a[l].x); } bool check(ll num)//因為我一個區(qū)間里的數(shù)不一定都要移到中位數(shù)來，有可能是左端點剩下了，有可能是右端點剩下了，所以我們分兩種情況， {ll num2=num/2+1;ll l=1,r=1,mid=1;while(1){while(r<=n&&prew[r]-prew[l-1]<num)r++;//計算直到物品數(shù)大于我們假想的結果那一段區(qū)間while(mid<=n&&prew[mid]-prew[l-1]<num2)mid++;//求出中位數(shù)的位置if(r>n||mid>n)break;ll s=cal_pre(l,mid)+cal_suf(mid,r-1)+(num-(prew[r-1]-prew[l-1]))*(a[r].x-a[mid].x);// 右端點可能會多plus個product,所以我們要減去沒用到的的一部分的花費if(s<=T)return true;l++;}l=r=mid=n;while(1){while(l>=1&&prew[r]-prew[l-1]<num)l--;//下面的計算方法同上，只是剩下的是左端點while(mid>=2&&prew[mid]-prew[l-1]<num2)mid--;if(l<1||mid<2)break;ll s=cal_pre(l+1,mid)+cal_suf(mid,r)+(num-(prew[r]-prew[l]))*(a[mid].x-a[l].x);if(s<=T)return true;r--;}return false; } int main() {scanf("%lld%lld",&n,&T);T/=2;ll l=0,r=0;for(ll i=1;i<=n;i++){scanf("%lld",&a[i].x);}for(ll i=1;i<=n;i++){scanf("%lld",&a[i].w);}for(ll i=1;i<=n;i++){prew[i]=prew[i-1]+a[i].w;//計算左邊的物品到當前位置的相關操作prec[i]=prec[i-1]+prew[i-1]*(a[i].x-a[i-1].x);}for(ll i=n;i>=1;i--){sufw[i]=sufw[i+1]+a[i].w;//計算右邊的物品到當前位置的相關操作sufc[i]=sufc[i+1]+sufw[i+1]*(a[i+1].x-a[i].x);r+=a[i].w;}while(l<r){ll mid=(l+r+1)>>1;if(check(mid)){l=mid;}else r=mid-1;}printf("%lld\n",l);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lis-/p/9377364.html

總結

以上是生活随笔為你收集整理的牛客多校第二场 G transform的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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