题目描述
给出
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】选数排列【二分の数论】
关注我们小说电影免费看关注我们,获取更多的全网素材资源,有趣有料!120000+人已关注
评论抢沙发