【洛谷2020.8.24SSL模拟赛T2】选数排列【二分の数论】


题目描述

给出

NN

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

R×CR×C

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

R×CR×C

R×C 的矩阵(

RR

R 行

CC

C 列)中。

我们先定义一个函数

D(i)D(i)

D(i) 代表第

ii

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

FF

F 为矩阵中

D(i)(1iR)D(i)(1≤i≤R)

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

我们需要

FF

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

FF

F 值是多少吗?

输入格式

第一行给出

33

3个整数

N,R,CN,R,C

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

接下来一行有

NN

N 个整数,代表

NN

N 个可以选择的数

PiP i

Pi 。

输出格式

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

FF

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系列小说

【洛谷2020.8.24SSL模拟赛T2】选数排列【二分の数论】

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【洛谷2020.8.24SSL模拟赛T2】选数排列【二分の数论】
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏