最后一个样例不对
查看原帖
最后一个样例不对
1244320
Delayed楼主2025/2/6 17:55
#include <bits/stdc++.h>
using namespace std;
int lengh,l,r,m,n,a[500005];
//k<m mid(min)--l=mid+1;
//k==m l=mid+1
//k>m mid(max)--r=mid-1
int main(){
	cin>>lengh>>n>>m;
	int now,before=0;
	for(int i=0;i<n;i++)
	{
		cin>>now;
		a[i]=now-before;
		before=now;
	}
	a[n]=lengh-before;
	l=1;
	if(n==m)
	{
		cout<<lengh;
		return 0;
	}
	r= lengh / (n-m);
	while(l<=r)
	{
		int mid=(l+r)/2;
		int tmp,k=0;
		for(int i=0;i<=n;i++)
		{
			tmp=a[i];
			while(tmp<mid && i<n)
			{
				i++;
				tmp+=a[i];
				k++;
			}
		}
		if(k<=m)l=mid+1;
		else r=mid-1;
	}
	cout<<r;
	return 0;
}

8 3 1
2
4
7
//正解输出 2
//输出 3
2025/2/6 17:55
加载中...