題干：

某班有?nn?個同學，每個同學有一個外向程度?a_iai?。由于要進行某個活動，需要把他們分成若干個小組，每個小組的人數(shù)至少為?mm?人。不同外向程度的人在一個小組會產(chǎn)生不開心值，定義一個小組的不開心值為組內(nèi)成員外向程度最大值和最小值的差，一個班級的不開心值為所有小組不開心值的最大值。

那么問題來了，如何分組使得班級的不開心值最小，請你求出這個最小的班級不開心值。

輸入格式

第一行兩個整數(shù)?n,mn,m，分別表示人數(shù)和每個小組最少的人數(shù)要求。

第二行?nn?個整數(shù)?a_iai?，表示每個同學的外向程度。

輸出格式

一個整數(shù)，表示最小的班級不開心值。

數(shù)據(jù)范圍

對于?30\%30%?的數(shù)據(jù)：1\le m \le n \le 201≤m≤n≤20，1\le a_i \le 1001≤ai?≤100。

對于?60\%60%?的數(shù)據(jù)：1\le m \le n\le 10001≤m≤n≤1000，1\le a_i \le 10001≤ai?≤1000。

對于?100\%100%?的數(shù)據(jù)：1\le m\le n \le 5\cdot10^51≤m≤n≤5?105，1\le a_i \le 10^91≤ai?≤109。

樣例解釋

第一個樣例，只要每個人各自一個組，不開心值就都是?00。

第二個樣例，最佳的分組情況為：9,119,11?一個組，6,3,56,3,5?一個組，兩個組的不開心值分別為?22?和?33，那么班級的不開心值為?33。

樣例輸入1復制

5 1 2 4 6 8 10

樣例輸出1復制

0

樣例輸入2復制

5 2 9 11 6 3 5

樣例輸出2復制

3

解題報告：

這題關鍵在于怎么check。我們用dp[i]代表：對前i個人進行劃分，最后一個可以進行分組的（可以被塞進某個分組的）人的編號。

考慮最后一個人，判斷當前第i個人能不能作為當前分組的最后一個人，這就需要找之前分完組后第一個沒組可歸的人的編號?即dp[i-m]+1。如果能作為最后一個人，那dp[i]=i,否則就是dp[i-1]。

?

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 6e5 + 5; int n, m; int a[MAX], dp[MAX]; bool ok(int x) {// dp[0~m-1]=0for (int i = m; i <= n; i++) {if (a[i] - a[dp[i - m] + 1] <= x) dp[i] = i;else dp[i] = dp[i - 1];}return dp[n] == n; } int main() {cin>>n>>m;for (int i = 1; i <= n; i++) scanf("%d", a+i);sort(a + 1, a + n + 1);int l = 0, r = 1e9;int mid = (l + r) >> 1;while (l < r) {mid = (l + r) >> 1;if (ok(mid)) r = mid;else l = mid + 1;}printf("%d\n", l);return 0; }

另一個dp做法：

所有數(shù)據(jù)首先經(jīng)過排序。 我們?nèi)绻胐p[i]表示前i個數(shù)字在猜測答案x的條件下，是否能夠劃分成比m大的子集和。那么dp[i]可以去把l…r-1的一串數(shù)字染成true，l=i+m，r是第一個不滿足a[r]-a[i+1]<=x的位置（當然r可能小于或等于l，這時候不染色）。
?每check一次dp一次，返回的是dp[n]是否為true。
?然而這樣的話dp最差是n^2效率，可以想到用樹狀數(shù)組+掃描線或者線段樹來改進。但是五十萬的數(shù)據(jù)不允許兩個log存在。實際上可以發(fā)現(xiàn)由于我們的點查詢是從左到右連續(xù)的，所以沒必要搞樹狀數(shù)組，直接掃描線就行了，然后dp[i]就是i處的覆蓋區(qū)間數(shù)，也就是掃描線數(shù)組的前綴和，前綴和大于0相當于為true，否則為false。

原先做n^2的dp的話，是如果dp[i]是true的話，那么后面l~r-1也更新為true。

考慮到這個過程像是區(qū)間覆蓋，所以可以用端點處+1 ，-1，然后用前綴和來表示真正的dp值（這個前綴和也就是代碼里的pre，pre>0表示曾被true覆蓋過，，也就是原先意義下的dp[i]=true）。。

只要i是可以達到的，l~r-1就可以從i處增加一個子集來達到。

鏈接

#include<cstdio> #include<algorithm> #include<queue> #define M (L+R>>1) using namespace std;int n,a[500005],m,L,R,dp[500005];bool check(int x) {dp[0]=1;dp[1]=-1;for(int i=2;i<=n;i++)dp[i]=0;int pre=0;for(int i=0,j=1,l,r;i<=n;i++){pre+=dp[i];if(!pre)continue;while(j<=n&&a[j]-a[i+1]<=x)j++;l=i+m;r=j;if(l>=r)continue;dp[l]++;dp[r]--;}return pre>0; }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);L=0;R=a[n]-a[1];while(L<R)if(check(M))R=M;elseL=M+1;printf("%d",L); return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的*【计蒜客 - 蓝桥训练】人以群分（二分 + dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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