题目描述
在麦克雷的面前有N个数，以及一个R*C的矩阵。现在他的任务是从N个数中取出 R*C 个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现在，麦克雷想知道矩阵的最小法值是多少。
输入
输入共两行。
第一行是三个整数：n，r，c。（r, c <= 104, r * c <= n< = 106）
第二行是 n 个整数 Pi。(0 < pi <= 109)
输出
输出一个整数，即满足条件的最小的法值。
样例输入
7 2 3170 205 225 190 260 225 160样例输出
30思路: 暴力枚举（二分优化）
满足条件的法值 一定大于等于1, 小于 pi 中的最大值 Max。
从1~Max 这个范围内二分搜索最小的满足条件的法值。
bool judge(int v) ；
// v 作为最小法值能否成立
最坏时间复杂度我也算不出来，不过刚开始 judge 的循环次数接近于 r , 而后升高
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000100;
int a[N];
int n, r, c;
bool judge(int v) {
// v 作为最小法值能否成立
int Count = 0;
for(int i=c; i<=n; i++) {
if(a[i]-a[i-c+1] <= v) {
Count ++;
if(Count >= r) {
return true;
}
i = i+c-1;
}
}
return false;
}
int main(){
cin >> n >> r >> c;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
sort(a+1, a+n+1); // 排序
int left = 1, right = a[n];
int mid = (left+right)/2;
while(left < right) {
// 从1~Max 这个范围内二分搜索最小的满足条件的法值
// cout << mid << endl;
if(judge(mid))
right = mid;
else
left = mid+1;
mid = (right+left)/2;
}
cout << left << endl;
return 0;
}