Description

鄉間有一條筆直而長的路稱為“米道”。沿著這條米道上 R 塊稻田，每塊稻田的坐標均
為一個 1 到 L 之間(含 1 和 L)的整數。這些稻田按照坐標以不減的順序給出，即對于 0 ≤ i <
R，稻田 i 的坐標 X[i]滿足 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。?
注意：可能有多塊稻田位于同一個坐標上。?
我們計劃建造一個米倉用于儲存盡可能多的稻米。和稻田一樣，米倉將建在米道上，其
坐標也是一個 1 到 L 之間的整數（含 1 和 L）。這個米倉可以建在滿足上述條件的任一個位
置上，包括那些原來已有一個或多個稻田存在的位置。?
在收獲季節，每一塊稻田剛好出產一滿貨車的稻米。為了將這些稻米運到米倉，需要雇
用一位貨車司機來運米。司機的收費是每一滿貨車運送一個單位的距離收取 1 元。換言之，
將稻米從特定的稻田運到米倉的費用在數值上等于稻田坐標與米倉坐標之差的絕對值。?
不幸的是，今年預算有限，我們至多只能花費 B 元運費。你的任務是要幫我們找出一個
建造米倉的位置，可以收集到盡可能多的稻米。?

Input

第一行 三個整數 R L B
接下來R行 每行一個整數 表示X[i]

Output

一個整數 最多稻米數

Sample Input

5 20 6
1
2
10
12
14

Sample Output

3
HINT
1 ≤ R ≤ 100,000
1 ≤ L ≤ 1,000,000,000
0 ≤ B ≤ 2,000,000,000,000,000 解析：其實去畫一畫或想一下就會發現，米倉在兩個稻田間的任意位置，兩個稻田的運費之和都相等，那么我們不如直接考慮將它建在哪一塊稻田上。 二分枚舉稻田數x，然后用一個for循環來枚舉我們所假想收割的x個稻田中最左邊的那個稻田位置為l,然后通過x推出r,mi（最右邊的位置和中間位置）。谷倉在中間時為最優解（這個自己去試試畫出來想）所以谷倉位置為mi。好啦那么我們枚舉的這段區間的費用是多少呢？可能很多人會和我一樣第一反應是用一個for循環來計算，可是之前的枚舉已經是O(nlogn)了，這就決定了我們的計算最好復雜度為O（1）。我們用前綴和來實現。首先設費用為sum,f為一個數組，這個數組中f[i]儲存的是1~i塊稻田的坐標和，a數組用來儲存每塊稻田的坐標，設一個變量now來表示米倉的坐標（就是a[now]），則公式為： ??sum=now*(mi-l)-(f[mi-1]-f[l-1])+(f[r]-f[mi])-now*(r-mi);? 為什么這么做呢，下面來解釋一下。 我們需要把區間分成左右兩邊來做，左邊的費用等于=now-a[l]+now-a[l+1]+now-a[l+2]+....+now-a[mi-1];我們可以發現他是有多個now-a[?]組合而成，有幾項呢？不拿算出總共有mi-l(不是數字1是L！）項，則式子變為=now*(mi-l)-(a[l]+a[l+1]+a[l+2]+....+a[mi-1]);好啦那么a[l]+..+a[mi-1]即為第l塊稻田到第mi-1塊稻田的坐標之和，完全可以用前綴和直接表示成f[mi-1]-f[l-1],好啦左邊的式子最終成為：now*(mi-l)-(f[mi-1]-f[l-1])，同理右邊的式子也可以這樣推出來（不寫啦）。 算出sum后只要比B元小，就成立了，否則不成立。 程序： #include<iostream> #include<cstdio> using namespace std; long long f[100010],now,k,ans,a[100010],sum,n,l,b,lef,righ,mid; bool check(long long x) {int i,l,r,mi;for (i=1;i<=n-x+1;++i){l=i;（最左邊的稻田） r=i+x-1（最右邊的稻田）; mi=(l+r)/2（米倉）;now=a[mi];（米倉坐標）sum=now*(mi-l)-(f[mi-1]-f[l-1])+(f[r]-f[mi])-now*(r-mi); （式子的具體推法已經寫在上面了）if (sum<=b) return true;}return false; } int main() {cin>>n>>l>>b;for (int i=1;i<=n;++i) cin>>a[i];f[0]=0;for (int i=1;i<=n;++i) f[i]=f[i-1]+a[i];（前i個稻田的坐標之和）lef=0;righ=n+1;ans=0;while (lef<=righ) （枚舉有幾塊稻田能收割）{mid=(lef+righ)/2;if (check(mid)==true) {lef=mid+1;if (ans<mid) ans=mid;}else righ=mid-1;} cout<<ans<<endl;return 0; }

好啦好啦。

轉載于:https://www.cnblogs.com/2014nhc/p/6208118.html

總結

以上是生活随笔為你收集整理的2600: [Ioi2011]ricehubh的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。