有大佬知道附加的那个测试点是什么吗?其他过了,那个点超时了
查看原帖
有大佬知道附加的那个测试点是什么吗?其他过了,那个点超时了
840984
lansier楼主2023/1/3 15:52
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010], s[100010];
int n, l, k;
bool check(int x)
{
	int cnt = 0, temp = a[0];
	for (int i = 1; i <= n; i++){
		if (a[i] - temp > x) cnt++, temp += x, i--;
		else temp = a[i];
	}
	return cnt > k;
}
int main(void)
{
	cin >> l >> n >> k;
	int i, j, x=0, y, ll, rr;
	for (i = 1; i <= n; i++){
		cin >> a[i];
		s[i] = a[i] - a[i - 1];
		x = max(s[i], x);
	}
	ll = 0, rr = x;
	while (ll < rr)
	{
		int mid = ll + rr>> 1;
		if (check(mid)) ll=mid+1;
		else rr = mid ;
	}
	cout << rr << endl;
	system("pause");
	return 0;
}
2023/1/3 15:52
加载中...