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输入 #14 11 8.02 7.43 4.57 5.39输出 #12.00说明/提示对于100 % 100\%100%的数据0 L i ≤ 100000.00 , 0 n ≤ 10000 , 0 k ≤ 10000 0L_i\leq 100000.00,0n\leq 10000,0k\leq 100000Li​≤100000.00,0n≤10000,0k≤10000解题思路本题是二分答案 贪心判定的经典问题要求在N NN条绳子中切出K KK条等长的小段求小段的最大可能长度。由于答案具有单调性可通过二分长度并检查能否切出足够数量来逼近最优解最后通过格式化输出实现直接舍去多余小数位。1. 问题等价转化目标求一个长度x xx使得∑ i 1 N ⌊ L i / x ⌋ ≥ K \sum_{i1}^N \lfloor L_i / x \rfloor \ge K∑i1N​⌊Li​/x⌋≥K且x xx尽可能大。单调性若长度为x xx时能切出至少K KK段则任何小于x xx的长度也必然能满足反之若x xx无法切出足够段数所有大于x xx的长度也不行。因此可以对长度进行二分搜索。判定函数给定长度x xx计算每条绳子能切出的段数向下取整累加后与K KK比较即可。2. 算法实现确定二分范围下界L 0 L 0L0上界R RR设为所有绳子长度之和或最大绳长和足够大即可。二分循环当R − L 10 − 4 R - L 10^{-4}R−L10−4时精度足够取m i d ( L R ) / 2 mid (L R) / 2mid(LR)/2。若chk(mid)为真能切出至少K KK段则答案至少为m i d midmidL m i d L midLmid否则R m i d R midRmid。处理输出精度题目要求直接舍去两位小数之后的部分而非四舍五入。可采用以下方法将二分得到的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)存储绳子长度。总结利用二分答案将“求最大长度”转化为“能否切出足够段数”的判定每次判定线性扫描计算总段数。最后通过字符串处理实现“直接舍去”的截断输出精确满足题目格式要求。代码简要说明chk(x)函数遍历每条绳子长度a i a_iai​累加⌊ a i / x ⌋ \lfloor a_i / x \rfloor⌊ai​/x⌋返回是否≥ K \ge K≥K。二分主循环L 0 L0L0R RR初始为所有绳长之和。不断取中点并调用chk更新上下界直至R − L ≤ 10 − 4 R-L \le 10^{-4}R−L≤10−4。输出处理用sprintf(buf1, %.3f, L)将最终长度转为三位小数字符串然后通过buf[strlen(buf1)]\0截断第三位小数再打印buf1实现直接舍去。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,k;doublea[10005],L,R,mid;charbuf[100];boolchk(doublex){ll tot0;for(ll i1;in;i)tot(ll)floor(a[i]/x);returntotk;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,k);L0.0;R0.0;for(ll i1;in;i){scanf(%lf,a[i]);Ra[i];}while(R-L1e-4){mid(LR)/2.0;if(chk(mid))Lmid;elseRmid;}sprintf(buf1,%.3f,L);buf[strlen(buf1)]\0;printf(%s,buf1);return0;}