【JZOJ4790】【NOIP2016提高A组模拟9.21】选数问题

题目描述

在麦克雷的面前有N个数，以及一个R*C的矩阵。现在他的任务是从N个数中取出R*C个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现在，麦克雷想知道矩阵的最小法值是多少。

输入

输入共两行。
第一行是三个整数：n，r，c。
第二行是 n 个整数 Pi。

输出

输出一个整数，即满足条件的最小的法值。

样例输入

7 2 3
170 205 225 190 260 225 160

样例输出

30

数据范围

30%：1<=n,r,c<=100
50%：1<=n,r,c<=1000
100%：1<=r,c<=10^4,r*c<=n<=5*10^5,0

解法

考虑矩阵中的两行a和b，a1<a2<...<aC，b1<b2<...<bC，如果aC>b1，那么交换aC和b1可以得到更优的答案。
所以每一行的值域是不会有交集的。

---

将所有数升序排序。
设已知答案为ans；
顺序枚举每一个数，如果a[i+C−1]−a[i]<=ans，我们就可以贪心地把这C个数放进矩阵，枚举完后判断一下是否能够凑齐R行。
证明：
设选取a[i+k]..a[i+k+C-1]会比选取a[i]..a[i+C-1]更优。
设f(x)为[x..n]的最大答案。
那么选取a[i+k]..a[i+k+C-1]能够得到的最大答案即为f(i+k+C)+1；
选取a[i+k]..a[i+C-1]能够得到的最大答案即为f(i+C)+1；
显然f(x)是减函数。
所以与假设违背。

---

二分答案ans。
就可以将原问题转化为上述问题。

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define ln(x,y) int(log(x)/log(y))
#define sqr(x) ((x)*(x))
using namespace std;
const char* fin="aP1.in";
const char* fout="aP1y.out";
const int inf=0x7fffffff;
const int maxn=500007;
int n,m1,m2,i,j,k,tmp,ans,cnt,tmd,l,r,mid;
int a[maxn];
bool judge(int limit){
    int i,j,k;
    cnt=0;
    for (j=1;j<=n-m2+1;j++){
        if (a[j+m2-1]-a[j]<=limit){
            cnt++;
            j=j+m2-1;
            if (cnt>=m1) return true;
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m1,&m2);
    for (i=1;i<=n;i++) scanf("%d",&a[i]),r=max(r,a[i]);
    sort(a+1,a+n+1);
    l=0;
    while (l<r){
        mid=(l+r)/2;
        if (judge(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}

启发

最值套最值可以考虑二分。