题面
在麦克雷的面前有 N 个数, 以及一个 R*C 的矩阵. 现在他的任务是从 N 个数中取出 R*C 个, 并填入这个矩阵中. 矩阵每一行的法值为本行最大值与最小值的差, 而整个矩阵的法值为每一行的法值的最大值. 现在, 麦克雷想知道矩阵的最小法值是多少.
- 30%:1<=n,r,c<=100
- 50%: 1<=n,r,c<=1000
- 100%:1<=r,c<=10000,r*c<=n<=5*100000,0<p<1e9
分析
一眼题, 最大值最小, 数据 1e5,99.9% 是二分.
于是考虑怎么 check? 只需要排序, 贪心思想, 统计当前的数与它刚好相隔 c-1 的数的差是否小于 check 的值, 再统计有多少组满足, 看能否达到 r 组
代码
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define N 500500
- int n,k,c,l,r,mid;
- int a[N];
- inline void read(int &x)
- {x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
- while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();}
- inline int check(int x)
- {
- int i=1,ok=0,gro=0;
- while(i<=n)
- {
- if(i+c-1<=n&&a[i+c-1]-a[i]<=x)gro++,i+=c;
- else i++;
- if(gro>=k){ok=1;break;}
- }
- if(ok)return 1;
- return 0;
- }
- int main()
- {
- read(n);read(k);read(c);
- for(int i=1;i<=n;i++)read(a[i]);
- sort(a+1,a+1+n);
- l=0,r=a[n];
- while(l<r)
- {
- mid=l+r>>1;
- if(check(mid))r=mid;
- else l=mid+1;
- }
- printf("%d",r);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2806796.html