题目描述

给出

N 个数，我们需要选择其中的

R×C 个数,，把它们填入一个

R×C 的矩阵（

R 行

C 列）中。

我们先定义一个函数

D(i) 代表第

i行中最大的数和最小的数之差。对于整个矩阵，定义

F 为矩阵中

D(i)(1≤i≤R) 的最大值。

我们需要

F 的值最少，你能求出最少可能达到的

F 值是多少吗？

输入格式

第一行给出

3个整数

N,R,C，对应题目中描述的参数。

接下来一行有

N 个整数，代表

N 个可以选择的数

Pi 。

输出格式

输出一行表示最少可能达到的

F 值。

输入输出样例

输入 #1

7 2 3

170 205 225 190 260 225 160


输出 #1
30



分析：

二分+模拟

先排序 保证单调 然后二分

二分最大差值 看看当前最大差值<最大差值 并满足行数

保证枚举是合法的 输出即可
CODE：
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

long long a[1000010],f[1000010];

long long n,r,c;

bool check(int qwq)

{

	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]<=qwq)    //当前差值<最大差值

	     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<r)  //二分

     {

     	mid=(l+r)>>1;

     	if(check(mid))

     	  r=mid;

     	else

     	  l=mid+1;

     }

    cout<<l;

    return 0;

}


原创：https://www.panoramacn.com

源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。
专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说


免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可->
联系客服
投诉资源
 www.panoramacn.com资源全部来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系站长并出示版权证明以便删除。
敬请谅解！ 侵权删帖/违法举报/投稿等事物联系邮箱：2640602276@qq.com
                
                
未经允许不得转载：书荒源码源码网每日更新网站源码模板！ » 【洛谷2020.8.24SSL模拟赛T2】选数排列【二分の数论】
                                
                                    
【洛谷2020.8.24SSL模拟赛T2】选数排列【二分の数论】
                                
                    

        

            
            
关注我们小说电影免费看
            
关注我们，获取更多的全网素材资源，有趣有料！
            
120000+人已关注
        
    
 
                
                    


                    
分享到：
        
                                赞(0)
        
                    打赏