題干：

鏈接：https://ac.nowcoder.com/acm/contest/886/D
來(lái)源：牛客網(wǎng)
?

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi?. He can pack all these items into at most K boxes of the same volume.
?

TangTang is so clever that he uses the following strategies for packing items:

?

- Each time, he would put items into a box by the next strategy, and then he would try to fill another box.

- For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.

Now, the question is what is the minimum volume of these boxes required to pack all items.

輸入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤201 \leq T \leq 201≤T≤20), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, K (1≤n,K≤10001 \leq n, K \leq 10001≤n,K≤1000), representing the number of items and the number of boxes respectively.The second line contains n integers v1v_1v1?, v2v_2v2?, …\ldots…, vnv_nvn? (1≤v1,v2,…,vn≤10001 \leq v_1, v_2, \ldots, v_n \leq 10001≤v1?,v2?,…,vn?≤1000), where the i-th integer viv_ivi? represents the volume of the i-th item.

輸出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

輸入

復(fù)制

1 5 3 1 2 3 4 5

輸出

復(fù)制

Case #1: 5

題目大意：

你有n件行李，有k個(gè)箱子體積相同的箱子，遵循下面的規(guī)則將行李放進(jìn)箱子里面，每次都取當(dāng)前最大的可以放進(jìn)箱子的行李放進(jìn)箱子，如果該箱子放不進(jìn)任何行李那么就換一個(gè)新的箱子再按照這一條規(guī)則進(jìn)行放行李，請(qǐng)問(wèn)箱子最小的體積是多少，可以放進(jìn)所有行李。

解題報(bào)告：

打眼一看是二分，但是其實(shí)并沒(méi)有單調(diào)性，大概這么理解：假設(shè)是這些行李，你如果箱子的體積減小一點(diǎn)，或許就能拿出來(lái)一個(gè)大行李，放進(jìn)去更多的小行李。這樣導(dǎo)致后面的箱子需要放的行李的序列和 不減小箱子體積的行李序列是完全不一樣的了，所以答案肯定也會(huì)不同，所以不能二分。

這題的正解是我們可以確定一個(gè)下界和一個(gè)上界，并且這個(gè)界的范圍不會(huì)很大，所以可以直接在這個(gè)上下界內(nèi)暴力就好。

當(dāng)然由于不具有二分性質(zhì)的樣例不好構(gòu)造，我們可以近似認(rèn)為這是一個(gè)具有二分性質(zhì)的題目，只不過(guò)加點(diǎn)隨機(jī)化的思想。注意這題如果先二分完了在最后進(jìn)行隨機(jī)數(shù)處理的話也過(guò)不去，需要在二分的過(guò)程中擴(kuò)大搜索范圍。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5;int a[MAX]; int n,k; bool ok(int x) {multiset<int> ms;int cnt = 0,res = x;for(int i = 1; i<=n; i++) ms.insert(a[i]);while(1) {if(ms.empty() || cnt == k) break;auto it = ms.upper_bound(res);if(it == ms.begin()) {res = x;cnt++;} else {--it;res -= *it;ms.erase(it);}}if(ms.empty()) return 1;else return 0; } int main() {int t,iCase=0;cin>>t;while(t--) {scanf("%d%d",&n,&k);for(int i=1; i<=n; i++) scanf("%d",a+i);int l = 1,r=1e6,ans=1e6,mid;while(l+20<=r) {mid=(l+r)>>1;int flag = 0;for(int i = mid; i<=mid+10; i++) {if(ok(i)) {flag = 1,r = i-1,ans=i;break;}}if(flag == 0) l = mid+1;}for(int i = max(0,ans-20); i<=ans; i++) {if(ok(i)) {printf("Case #%d: %d\n",++iCase,i);break;}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第六场）- D】Move（随机化二分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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