【題目鏈接】

ybt 1242：網(wǎng)線主管
OpenJudge NOI 1.11 04:網(wǎng)線主管

【題目考點(diǎn)】

1. 二分答案

【解題思路】

看題目中的數(shù)據(jù)都帶小數(shù)點(diǎn)，似乎這是實(shí)數(shù)域上的問題。但仔細(xì)分析，該題的輸入數(shù)據(jù)精確到厘米，要求輸出結(jié)果精確到厘米，實(shí)際只要在處理過程中保持為以厘米為單位，那么該問題本質(zhì)上是整數(shù)域的問題。

用二分思想考慮該問題，題目問：要找最長的網(wǎng)線長度。對應(yīng)的模板為：求滿足某一條件的最大值。
網(wǎng)線長度需要滿足的條件為：將庫存中的網(wǎng)線按該長度進(jìn)行切割，得到的網(wǎng)線數(shù)量大于等于居民需要的網(wǎng)線數(shù)量。
假設(shè)要判斷為網(wǎng)線長度為x是否滿足條件，先遍歷所有庫存中網(wǎng)線長度，每條網(wǎng)線長度記為l，那么l/x（整除運(yùn)算）即為這條庫存網(wǎng)線可以切出的成品網(wǎng)線的條數(shù)，加和求出總條數(shù)。看處理得到的網(wǎng)線總條數(shù)是否大于等于居民需要的網(wǎng)線數(shù)量k，如果是，那么滿足條件，否則不滿足條件。

注意單位換算，計(jì)算過程用厘米為單位，輸出時(shí)轉(zhuǎn)用單位米。
二分查找時(shí)，網(wǎng)線長度最小值設(shè)為0，最大值為$100km=10^{7}cm$，考慮極端情況，假設(shè)庫存中每條網(wǎng)線都是$10^{7}cm$，一共有$10^4$條，而要切成$1cm$的網(wǎng)線，共有$10^7?10^4=10^{11}$條網(wǎng)線，超出了int的范圍。所以網(wǎng)線計(jì)數(shù)變量要設(shè)為long long。

【題解代碼】

解法1：二分答案

#include <bits/stdc++.h> using namespace std; int n, k, a[10005];//a[i]:第i條網(wǎng)線的長度 單位：厘米 bool check(int l)//如果需要網(wǎng)線長度為l，最多可以得的網(wǎng)線段數(shù)是否大于等于k {long long ct = 0;//計(jì)數(shù)for(int i = 1; i <= n; ++i)ct += a[i] / l;//整除運(yùn)算return ct >= k; } int main() {double t; cin >> n >> k;for(int i = 1; i <= n; ++i){cin >> t;a[i] = t * 100;//單位：厘米}if(check(1) == false)//如果切成1厘米一段也不能達(dá)到要求的數(shù)量，則沒有切割方案 {cout << "0.00";return 0;} int l = 1, r = 1e7, m;while(l < r)//二分答案求滿足條件的最大值{m = (l + r + 1) / 2;if(check(m))//如果網(wǎng)線長為m滿足條件l = m;elser = m - 1;}cout << fixed << setprecision(2) << (double)l / 100;//單位轉(zhuǎn)為米return 0; } 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1242：网线主管 | OpenJudge NOI 1.11 04:网线主管的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。