Description

印度洋暖流溫潤著紐約，四季豐沛的雨水造就了一望無際的大草原。蒙古包是紐約最獨特的一道風(fēng)景線，每至二月中旬，紐約的土著傣族人民又開始半年一度的轉(zhuǎn)場了。
由于牲畜和行李過多，牧民 Azone 不得不多次往返于兩個草場之間運輸家當(dāng)。為了順利轉(zhuǎn)場，Azone 決定花費 w 元津巴布韋幣，購買一輛載重為 w 的汽車。共有 n 件家具需要搬運，每件家具的重量為 wi 。Azone 每次出發(fā)前，會搬若干件總重不超過 w 的物品上車：出發(fā)前，車是空載的，Azone 會選擇能搬上車的家具中最重的一件放上車(即該家具之前還未運走且放置該家具后汽車不會超載），然后在剩下的家具中繼續(xù)選擇一件能被搬走的最重的上車，持續(xù)裝車，直至剩下的家具都塞不上車。裝載完畢后，Azone 會開車運走這些家具，卸在目的地，再駕空車返回繼續(xù)運送，直至轉(zhuǎn)場完畢。
Azone 希望在運送次數(shù)不超過 R 的情況下完成轉(zhuǎn)場，求 Azone 最少需要購置價值多少的車。

Input

第一行，兩個整數(shù) n 和 R，分別表示家具件數(shù)及最多運送次數(shù)。
第二行，若干個整數(shù) wi ，表示家具重量。

Output

一行，表示答案。

Sample Input

6 2
26 7 10 30 5 4

Sample Output

42

Data Constraint

subtask 1 60pts，R,n,w i ≤ 20。
subtask 2 40pts，沒有額外限制。
對于100% 的數(shù)據(jù)，1 ≤ R,n,wi ≤ 2000。

Solution

• 考場上看到這題，哇，二分答案啊，拍都沒拍就交了。

• 結(jié)果——WA 60分！

• 不能直接二分啊！

• 對于本題，我們并不能證明對于一個合法容量 W ，W+1 也合法（剛好卡住的情況）。

• 我們設(shè)最優(yōu)答案為 C ，再令 mx=Max{wi} 。

• 于是我們可以證明所有 W≥C+wi 一定合法（因為每次都一定可以多裝點）。

• 那么我們隨便二分一個答案 T （注意不一定 T 就是最優(yōu)的）。

• 此時所有 W<T?mx 一定不合法。

• 那么我們暴力檢驗 mx 個，在區(qū)間 [T?mx,T] 中選一個最優(yōu)的即可。

• 在判斷一個容量 W 是否合法時，

• 可以用一個 multiset 每次 O(logN) 的查找出能裝的最大的那個。

• 即可以 O(N?log?N) 判斷。

• 時間復(fù)雜度 O(N2?log?N) 。

Code

#include<cstdio> #include<cctype> #include<set> using namespace std; const int N=2005; int n,R,mx,ans; int w[N]; multiset<int>s; multiset<int>::iterator it; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline bool check(int x) {s.clear();for(int i=1;i<=n;i++) s.insert(w[i]);int cnt=0;while(!s.empty()){int sum=x;while(!s.empty() && sum>=*s.begin()){it=s.upper_bound(sum);it--;sum-=*it;s.erase(it);}if(++cnt>R) break;}return cnt<=R; } int main() {freopen("newyork.in","r",stdin);freopen("newyork.out","w",stdout);n=read(),R=read();int l=0,r=0;for(int i=1;i<=n;i++){r+=w[i]=read();mx=max(mx,w[i]);}while(l<=r){int mid=l+r>>1;if(check(mid)){r=mid-1;ans=mid;}else l=mid+1;}for(int i=ans-mx;i<ans;i++)if(check(i)) return 0&printf("%d\n",i);printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5677. 【GDOI2018Day2模拟4.21】纽约的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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