题意： 长度为 n 的 a[] 序列，要你划分成多个连续的部分，每一部分至少有 k 个数。对于每一部分，其权值为最大值减最小值。最后总的权值为每一部分权值的最大值，求出可能的最小的总权值。
tags： 二分是肯定的，但没想到 dp 去 check 。。
先对 a[] 排序，二分 mid 时，dp[i] 记录前 i 个位置中最后一个满足条件的位置。也就是说 dp[i] 要存储一个位置j，满足j<=i, 且 [1,j] 这个子区间得到的答案不超过mid。
转移即：
dp[i] = dp[i-1];
if(i-k>=0 && a[i]-a[dp[i-k]+1]<=x) dp[i] = i;
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 300005; int n, k, a[N], dp[N]; bool check(int x) { dp[0]=0; rep(i,1,n) { dp[i] = dp[i-1]; if(i-k>=0 && a[i]-a[dp[i-k]+1]<=x) dp[i] = i; } return dp[n] == n; } int main() { scanf("%d%d", &n, &k); rep(i,1,n) scanf("%d", &a[i]); sort(a+1, a+1+n); int l=0, r=1e9, mid, ans; while(l<=r) { mid = l+r>>1; if(check(mid)) ans=mid, r=mid-1; else l=mid+1; } printf("%d\n", ans); return 0; }