ACWing-680 剪绳子 题解

题目大意

有N根绳子，第i根绳子长度为$Li$，现在需要M根等长的绳子，你可以对N根绳子进行任意裁剪（不能拼接），请你帮忙计算出这M根绳子最长的长度是多少。

解题思路

刚开始看到这个题意，想着应该是二分。

但是这个题目是浮点二分。

好久没写过浮点二分了，刚好补个博客。

浮点二分模板

while (r - l > 精度) {
	double mid = (l + r) / 2;//或者可以写成mid=l+(r-l)/2，防止溢出
	if (check(mid) >= m) l = mid;
	else r = mid;
}
printf("%.2lf", l);

顺便补个整数二分模板（y总的）

模板一：

当我们将区间$[l, r]$划分成$[l, mid]$和$[mid + 1, r]$时，其更新操作是$r = mid$或者$l = mid + 1$，计算$mid$时不需要加1。

while (l < r)
{
	int mid = (l + r) >> 1;
	if (check(mid)) r = mid;
	else l = mid + 1;
}
cout << l << endl;

模板二：

当我们将区间$[l, r]$划分成$[l, mid - 1]$和$[mid, r]$时，其更新操作是$r = mid - 1$或者$l = mid;$，此时为了防止死循环，计算$mid$时需要加1。

while (l < r)
{
	int mid = (l + r + 1) >> 1;
	if (check(mid)) r = mid;
	else l = mid + 1;
}
cout << l << endl;

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int num[N];
int n, m;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int cal(double x) {
	int ans = 0;
	rep(i, 1, n) {
		ans += num[i] * 1.0 / x;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	cin >> n >> m;
	rep(i, 1, n) cin >> num[i];
	double l = 0, r = 1e9;
	while (r - l > 1e-3) {
		double mid = (l + r) / 2;
		if (cal(mid) >= m) l = mid;
		else r = mid;
	}
	printf("%.2lf", l);
	return 0;
}