很长时间没有考过试了所以今天很激动 且考完试改完题不想做题所以过来写博客虚度光阴QAQ

传送门（校内）

题目大意

有$N$ 个数，以及一个$R\ast C$的矩阵。现在从$N$个数中取出$R\ast C$个，并填入这个矩阵中。矩阵每一行的值被定义为本行最大值与最小值的差，而整个矩阵的值被定义为为每一行的值的最大值。求矩阵的最小值。

1≤R,C≤10⁴，R∗C≤N≤5∗10⁵，0<pi≤10⁹

部分分解法（比如说50分）

那么考场上我的第一想法是DP(装作看不见数据范围

首先把整个序列从小到大排序，很容易发现最后的答案一定是连续的某几段（感性认识即可，证明好像也不难）

那么我们就考虑从这一个序列中挑出连续的$R$段，每段$C$个数，使得每一行的最小值最小。

那么我们用$w[i]$ 从第i个数开始选择k个数的极差

用$dp[i][j]$表示选择从第$i$个开始的$C$个数，已经选了$j$组这样的数。

（我就是在这里犯了傻，看了眼数据范围，拿最大值一除，以为这个$j$只有五十多）

很快能得到转移方程 $dp[i][j]$=$max(dp[k][j-1],w[i])$,其中K要遍历$1$ ~ $(i-C-1)$

考虑到这样的话复杂度是N^2，明显过不了，然后发现我们的$i$是从1~N的，所以再记一个$b[i][j]$来表示 在1~i 的范围内，选 j 组数的最优方案的结果。

$b[i][j]$=$min(b[i-1][j],dp[i][j])$

大功告成，如果我们把 j 当成50，这个算法的复杂度就是$O（N\ast 50）$

然后我满心欢喜的觉得自己过了

正解

其实，我刚才扯那么多半点用没有。

你以为这是个DP题？不你错了，这就是个**二分题而已。

我们二分答案，每次跑一遍，复杂度$O(NlogN)$

大功告成，上代码：

#include<bits/stdc++.h> #define rint register int #define ivoid inline void #define iint inline int #define endll '\n' #define ll long long using namespace std; const int N=5e5+5; const int M=3e3+5; const int inf=0x3f3f3f3f; int n,m,u,v,w,x,y,z; int a[N],sum,tot,res,l,r,mx,my,ans,num; iint rad() { int x=0,f=1;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x*f; } iint check(int s) { int x1=a[1],tot=0; int l=1; while(l+y-1<=n){ if(a[l+y-1]-a[l]>s)l++; else tot++,l=l+y; } return tot; } int main() { n=rad();x=rad();y=rad(); for(rint i=1;i<=n;i++)a[i]=rad(); sort(a+1,a+n+1); int l=1,r=a[n],mid,ans=inf,t=0; while(l<r){ mid=(l+r)>>1; t=check(mid); if(t<x)l=mid+1; else ans=mid,r=mid; } cout<<ans; }

总结

之所以我做错了还要把做错的方法放上来，emm

是因为貌似这种解法适用于另一类题？？反正我就是觉得这DP思路挺正，如果不是因为那个神奇的 j 我多半就可以过了对吧（疯狂找借口

总之，做题的时候一定一定不要想太多，能简单做就简单做，想多了不但会出事，而且还过不了QAQ