关于二分答案
  • 板块学术版
  • 楼主wwhOvO
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/1/8 23:15
  • 上次更新2023/11/5 05:01:23
查看原帖
关于二分答案
204619
wwhOvO楼主2021/1/8 23:15

工地现有 n 根钢管,第 i 根钢管的长度为 a[i]

现在想用这 n 根钢管来做一个支撑用的柱子。我么可以切割这些钢管成为更短的钢管,但是不能缝合两根钢管。为了安全起见,柱子必须用 至少 k 根长度相同的钢管加上混凝土制成,并且要求钢管长度必须为 整数。

问 这个柱子最高能建成多高(钢管可以有剩余)


这个题,为啥这么写可以

#include <cstdio>
#include <algorithm>
typedef long long ll;

const int MAXN = 1e+5;

int n, k;
ll a[MAXN + 15], l, r;

bool check(ll x) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		ll p = a[i] / x;
		cnt += p;
	}
//	printf("x = %lld, cnt = %d\n", x, cnt);
	return cnt >= k;
}

int main() {
	freopen("rope.in", "r", stdin);
	freopen("rope.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		r = std::max(r, a[i]);
	}
	
	l = 1; r++;
	while (l < r) {
		ll mid = ll(ll(l + r) / 2);
		if (check(mid)) l = mid + 1;
		else r = mid;
//		printf("l = %lld, r = %lld\n---------\n", l, r);
	}
	
	printf("%lld\n", r - 1);
	
	return 0;
} 

然后写

l = mid
r = mid - 1
printf("%lld\n", l);

就不行

求助

(最近脑子比较乱,语言组织可能出了点问题请谅解 qaq)

2021/1/8 23:15
加载中...