#5#6 WA 不知道为什么 求调 感谢!!!
查看原帖
#5#6 WA 不知道为什么 求调 感谢!!!
1528611
Happiness_3楼主2024/12/12 16:43
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll L,n,m;
const ll N = 5e4 + 10;
vector<ll> d(N);
vector<ll> a(N);

ll check(ll mid){
	ll tm = m;
	vector<ll> td(N);
	for(ll i = 1 ; i <= n ; ++i){
		td[i] = d[i];
	}
	for(ll i = 2 ; i <= n ; ++i){
		if(td[i] < mid){
			tm--;
			td[i+1] += td[i];
		}
	}
	if(L - a[n] < mid) tm--;
	if(tm < 0) return 0;
	return 1;
}

signed main(){
	cin >> L >> n >> m;
	for(ll i = 1 ; i <= n ; ++i){
		cin >> a[i];
	}
	d[1] = a[1];
	for(ll i = 2 ; i <= n ; ++i){
		d[i] = a[i] - a[i-1];
	}
	ll l = 1 , r = L ;
	ll mid;
	ll ans;
	while(l <= r){
		mid = (l + r) / 2;
		if(check(mid)){
			ans = mid;
			l = mid + 1;
		}
		else{
			r = mid - 1;
		}
	}
	cout << ans << endl;
	return 0;
}
2024/12/12 16:43
加载中...