T145305 【2020.8.24NOIP模拟赛】选数排列【二分】-白红宇

T145305 【2020.8.24NOIP模拟赛】选数排列【二分】

阅读量：340 次

发布时间：2019-03-04

本文共 630 字，大约阅读时间需要 2 分钟。

在这里插入图片描述

这道题看到最大数和最小数可以想到二分。

我们二分一个最大差值，定义一个

f

数组看看当前的最大差值能否满足行数

只有当当前差值

<

最大差值才能保证枚举的这一行是合法的。

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;long long a[1000010],f[1000010];long long n,r,c;bool check(int maxx){   	for(int i=0; i<=c-1; i++)	   f[i]=0;	for(int i=c; i<=n; i++)	 {   	   f[i]=f[i-1];   //赋初值	   if(a[i]-a[i-c+1]<=maxx)  //当前差值
        <最大差值才能保证枚举的这一行是合法的。 f[i]="f[i-c]+1;" } if(f[n]>
         =r) //满足行数要求 return 1; else return 0;}int main(){ cin>>n>>r>>c; for(int i=1; i<=n; i++) scanf("%lld",&a[i]); sort(a+1,a+1+n); int l=0,r=a[n]-a[1],mid; while(l
         
          >1; if(check(mid)) r=mid; else l=mid+1; } cout<