题目描述
寻找最大的符合条件值,选择整数二分模板二。
VJ上要sort。
写了两个check函数:都基于贪心
1.差分法,通过差分数组顺序判断即可。不过每次都要重新赋值,很烦。
2.类似双指针的方式,不直接把差分结果算出来,动态得到需要的“差分”值,会快很多。
C++ 代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int N=5e4+10;
int a[N];
int d[N];
int s[N];
int L,m,n;
bool check(int mid)
{
for(int i=1;i<=m+1;i++)
{
d[i]=s[i];
}
int cnt=0;
for(int i=1;i<=m+1;i++)
{
if(mid>d[i])
{
cnt++;
d[i+1]+=d[i];
}
}
return cnt<=n;
}
bool check1(int mid)
{
int last = 0, cnt = 0;
for (int i = 1; i <= m; i ++ )
if (a[i] - last < mid) cnt ++ ;
else last = a[i];
return cnt <= n;
}
int main()
{
cin>>L>>m>>n;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+m);
a[m+1]=L;
for(int i=1;i<=m+1;i++)
{
d[i]=a[i]-a[i-1];
}
for(int i=1;i<=m+1;i++)
{
s[i]=d[i];
}
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout<<r<<endl;
return 0;
}