P1577 切绳子

网页链接

P1577 切绳子

题目描述

有N NN条绳子，它们的长度分别为L i L_iLi​。如果从它们中切割出K KK条长度相同的绳子，这K KK条绳子每条最长能有多长？答案保留到小数点后2 22位(直接舍掉2 22位后的小数)。

输入格式

第一行两个整数N NN和K KK，接下来N NN行，描述了每条绳子的长度L i L_iLi​。

输出格式

切割后每条绳子的最大长度。答案与标准答案误差不超过0.01 0.010.01或者相对误差不超过1 % 1\%1%即可通过。

输入输出样例 #1

输入 #1

4 11 8.02 7.43 4.57 5.39

输出 #1

2.00

说明/提示

对于100 % 100\%100%的数据0 < L i ≤ 100000.00 , 0 < n ≤ 10000 , 0 < k ≤ 10000 0<L_i\leq 100000.00,0<n\leq 10000,0<k\leq 100000<Li​≤100000.00,0<n≤10000,0<k≤10000

解题思路

本题是二分答案 + 贪心判定的经典问题，要求在N NN条绳子中切出K KK条等长的小段，求小段的最大可能长度。由于答案具有单调性，可通过二分长度并检查能否切出足够数量来逼近最优解，最后通过格式化输出实现直接舍去多余小数位。

1. 问题等价转化

• 目标：求一个长度x xx，使得∑ i = 1 N ⌊ L i / x ⌋ ≥ K \sum_{i=1}^N \lfloor L_i / x \rfloor \ge K∑i=1N​⌊Li​/x⌋≥K，且x xx尽可能大。
• 单调性：若长度为x xx时能切出至少K KK段，则任何小于x xx的长度也必然能满足；反之，若x xx无法切出足够段数，所有大于x xx的长度也不行。因此可以对长度进行二分搜索。
• 判定函数：给定长度x xx，计算每条绳子能切出的段数（向下取整），累加后与K KK比较即可。

2. 算法实现

1. 确定二分范围：下界L = 0 L = 0L=0，上界R RR设为所有绳子长度之和（或最大绳长，和足够大即可）。
2. 二分循环：当R − L > 10 − 4 R - L > 10^{-4}R−L>10−4时（精度足够）：
   • 取m i d = ( L + R ) / 2 mid = (L + R) / 2mid=(L+R)/2。
   • 若chk(mid)为真（能切出至少K KK段），则答案至少为m i d midmid，L = m i d L = midL=mid；
   • 否则R = m i d R = midR=mid。
3. 处理输出精度：题目要求直接舍去两位小数之后的部分（而非四舍五入）。可采用以下方法：
   • 将二分得到的L LL用sprintf格式化为三位小数；
   • 手动截断字符串，舍去第三位小数及之后的内容，保留两位小数输出。代码中通过将字符串末尾置'\0'并输出有效部分来实现。

3. 复杂度分析

• 时间复杂度：二分次数约O ( log ⁡ ( sum / eps ) ) ≈ 40 O(\log(\text{sum} / \text{eps})) \approx 40O(log(sum/eps))≈40次，每次判定需遍历所有N NN条绳子，总O ( N log ⁡ V ) O(N \log V)O(NlogV)。N ≤ 10 4 N \le 10^4N≤104，轻松通过。
• 空间复杂度：O ( N ) O(N)O(N)存储绳子长度。

总结

利用二分答案将“求最大长度”转化为“能否切出足够段数”的判定，每次判定线性扫描计算总段数。最后通过字符串处理实现“直接舍去”的截断输出，精确满足题目格式要求。

代码简要说明

1. chk(x)函数：遍历每条绳子长度a i a_iai​，累加⌊ a i / x ⌋ \lfloor a_i / x \rfloor⌊ai​/x⌋，返回是否≥ K \ge K≥K。
2. 二分主循环：L = 0 L=0L=0，R RR初始为所有绳长之和。不断取中点并调用chk，更新上下界，直至R − L ≤ 10 − 4 R-L \le 10^{-4}R−L≤10−4。
3. 输出处理：用sprintf(buf+1, "%.3f", L)将最终长度转为三位小数字符串，然后通过buf[strlen(buf+1)]='\0'截断第三位小数，再打印buf+1，实现直接舍去。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,k;doublea[10005],L,R,mid;charbuf[100];boolchk(doublex){ll tot=0;for(ll i=1;i<=n;i++)tot+=(ll)floor(a[i]/x);returntot>=k;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&k);L=0.0;R=0.0;for(ll i=1;i<=n;i++){scanf("%lf",&a[i]);R+=a[i];}while(R-L>1e-4){mid=(L+R)/2.0;if(chk(mid))L=mid;elseR=mid;}sprintf(buf+1,"%.3f",L);buf[strlen(buf+1)]='\0';printf("%s",buf+1);return0;}