警示后人(hack)
查看原帖
警示后人(hack)
1265992
zhangyuqi277h楼主2025/6/20 10:46
8 3 1
2
4
7

这是hack点数据

这是我的代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+100;
int lf,n,m,st[N],tmp[N];
bool chk(int t){
	int num=0;
	for(int i=0;i<n;i++) tmp[i]=st[i]-(i!=0?st[i-1]:0);
	tmp[n]=lf-st[n-1];
	for(int i=0;i<=n;i++){
		if(tmp[i]<t){
			num++;
			tmp[i+1]+=tmp[i];
		}
		if(num>m){
			return 0;
		} 
	}
	return 1;
}
int main(){
	cin >> lf >> n >> m;
	for(int i=0;i<n;i++){
		cin >> st[i];
	}
	sort(st,st+n); 
	int l=0,r=lf;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(chk(mid)) l=mid;
		else r=mid-1;
	}
	cout << l;
	return 0;
}

这是正确的。我的错误原因是上面的

tmp[n]=lf-st[n-1];

之前写成了

tmp[n]=lf;

也就是没有减掉最后一个端点导致最后一块石头到终点位置错误,仅供参考

2025/6/20 10:46
加载中...