見：P1577 切繩子 - 洛谷
題目描述
有?N?條繩子，它們的長度分別為?Li?。如果從它們中切割出?K?條長度相同的繩子，這?K?條繩子每條最長能有多長？答案保留到小數點后?2?位(直接舍掉?2?位后的小數)。
輸入格式
第一行兩個整數?N?和?K，接下來?N?行，描述了每條繩子的長度?Li??。
輸出格式
切割后每條繩子的最大長度。答案與標準答案誤差不超過?0.01?或者相對誤差不超過?1%?即可通過。
輸入輸出樣例
in：
4 11
8.02
7.43
4.57
5.39
out：
2.00說明/提示
對于?100%?的數據?0<Li?≤100000.00,0<n≤10000,0<k≤10000
第一步
code
#include<bits/stdc++.h>
using namespace std;
const int q=1e4+5;
int n,k;
double z[q];bool ch(double x){int ans=0;for(int i=0;i<n;i++){ans+=floor(z[i]/x);if(ans>=k) return true;}return false;
}int main(){cin>>n>>k;for(int i=0;i<n;i++) cin>>z[i];double l=0,r=1e9;while(r-l>=1e-4){double mid=l+(r-l)/2;if(ch(mid)) l=mid;else r=mid;}printf("%.2f",floor(l*100)/100);return 0;
}第二步
分析
問題背景與應用場景
這個問題在現實生活中有很多應用場景，比如：
- 電纜切割：將不同長度的電纜切割成若干等長的小段，以滿足至少
k段的需求，同時最大化每段的長度。 - 土地劃分：將不同面積的土地劃分為至少
k塊相等面積的小地塊，求最大可能的地塊面積。 - 布料裁剪：將不同長度的布料裁剪成至少
k條等長的布條，以最大化每條布條的長度。
代碼詳細分析
全局變量與常量定義
const int q=1e4+5;
int n,k;
double z[q];q是一個常量，表示數組的最大長度，這里設置為 10005，足夠處理題目中可能出現的最大數據量。n和k是兩個整數變量，分別表示材料的數量和需要切割出的段數。z[q]是一個雙精度浮點數數組，用于存儲每個材料的長度。
核心判斷函數ch(double x)
bool ch(double x){int ans=0;for(int i=0;i<n;i++){ans+=floor(z[i]/x);if(ans>=k) return true;}return false;
}這個函數的作用是判斷是否可以將所有材料切割成至少k段，每段長度為x。具體邏輯如下：
- 初始化計數器
ans為 0。 - 遍歷每個材料，計算該材料可以切割出多少段長度為
x的小段，使用floor(z[i]/x)確保結果為整數。 - 累加每段材料可切割的段數到
ans中。 - 如果在遍歷過程中發現
ans已經達到或超過k，則立即返回true，表示可以切割出足夠的段數。 - 如果遍歷完所有材料后
ans仍小于k，則返回false。
主函數main()
int main(){cin>>n>>k;for(int i=0;i<n;i++) cin>>z[i];double l=0,r=1e9;while(r-l>=1e-4){double mid=l+(r-l)/2;if(ch(mid)) l=mid;else r=mid;}printf("%.2f",floor(l*100)/100);return 0;
}主函數實現了二分查找算法，用于找到最大的可行切割長度，具體步驟如下：
- 讀取輸入數據：首先讀取材料數量
n和需要切割的段數k，然后讀取每個材料的長度并存儲在數組z中。 - 初始化二分查找的左右邊界：左邊界
l初始化為 0，右邊界r初始化為一個足夠大的值（1e9），確保包含所有可能的答案。 - 執行二分查找：在
r-l >= 1e-4的條件下循環，這個條件控制了二分查找的精度，當左右邊界的差距小于 1e-4 時停止循環。 - 計算中間值
mid：使用l + (r - l) / 2計算中間值，避免直接使用(l + r) / 2可能導致的溢出問題。 - 判斷中間值是否可行：調用
ch(mid)函數，如果返回true，說明中間值mid是一個可行解，更新左邊界l = mid；否則更新右邊界r = mid。 - 輸出結果：循環結束后，
l的值即為所求的最大可行切割長度，但需要保留兩位小數。使用floor(l*100)/100確保結果精確到小數點后兩位，然后使用printf("%.2f", ...)輸出結果。
算法思路與二分查找的應用
這個問題的核心思路是利用二分查找來高效地找到最優解。二分查找適用于這種最大化最小值或最小化最大值的問題，其關鍵在于能夠快速判斷一個給定的值是否可行。
具體來說，二分查找的應用場景需要滿足以下條件：
- 解空間具有單調性：在這個問題中，如果長度
x是可行的，那么所有小于x的長度也都是可行的；反之，如果長度x不可行，那么所有大于x的長度也都不可行。 - 存在明確的判斷條件：通過
ch函數可以快速判斷一個給定的長度是否可行。
二分查找的時間復雜度是 O (log (max_length))，其中 max_length 是右邊界的值。在每次迭代中，需要遍歷所有材料一次，時間復雜度為 O (n)，因此總的時間復雜度為 O (n log (max_length))，這使得算法在處理大規模數據時仍然高效。
精度控制與輸出處理
在處理浮點數二分查找時，精度控制是一個關鍵問題。代碼中使用r - l >= 1e-4作為循環條件，確保結果的精度在小數點后四位。這是因為在實際應用中，我們通常只需要保留兩位小數的結果，而額外的精度可以避免由于浮點數計算誤差導致的結果偏差。
輸出處理部分使用了floor(l*100)/100來確保結果精確到小數點后兩位。這是因為直接使用%.2f格式化輸出可能會進行四舍五入，而題目要求是直接截斷到兩位小數。例如，如果計算結果是 3.149，floor(3.149*100)/100會得到 3.14，而不是 3.15。
代碼優化與擴展
輸入驗證
當前代碼沒有對輸入進行驗證，在實際應用中可以添加輸入驗證以增強代碼的健壯性。例如：
if (k <= 0) {cout << "Error: k must be a positive integer." << endl;return 1;
}右邊界優化
初始右邊界設置為 1e9 可能過大，可以根據輸入數據動態設置右邊界，例如：
double max_z = 0;
for(int i=0;i<n;i++) {cin>>z[i];max_z = max(max_z, z[i]);
}
double l=0, r=max_z;這樣可以減少二分查找的迭代次數，提高效率。
處理無解情況
如果所有材料的總長度小于k，則無論如何都無法切割出k段，此時應輸出 0。可以在開始時添加檢查：
double sum = 0;
for(int i=0;i<n;i++) {sum += z[i];
}
if (sum < k) {cout << "0.00" << endl;return 0;
}代碼可讀性優化
可以添加注釋來提高代碼的可讀性，例如：
// 檢查是否可以將所有材料切割成至少k段，每段長度為x
bool ch(double x){// ... 函數體 ...
}// 主函數：二分查找最大可行切割長度
int main(){// ... 主函數體 ...
}復雜度分析
- 時間復雜度：O (n log (max_length))，其中 n 是材料的數量，max_length 是右邊界的值。
- 空間復雜度：O (n)，主要用于存儲材料長度的數組。
測試用例
以下是一些測試用例，可以幫助驗證代碼的正確性：
-
基本測試：
- 輸入：
n=3, k=4,?z=[10, 20, 30] - 輸出：
15.00 - 解釋：每段長度為 15 時，可切割出
0+1+2=3段，不足 4 段；每段長度為 14 時，可切割出0+1+2=3段，不足 4 段；每段長度為 13 時，可切割出0+1+2=3段，不足 4 段；每段長度為 12 時，可切割出0+1+2=3段，不足 4 段；每段長度為 11 時，可切割出0+1+2=3段，不足 4 段；每段長度為 10 時，可切割出1+2+3=6段，滿足條件，且為最大可行長度。
- 輸入：
-
邊界測試：
- 輸入：
n=1, k=1,?z=[5.0] - 輸出：
5.00 - 解釋：只有一段材料，長度為 5，切割成 1 段，最大長度為 5。
- 輸入：
-
精度測試：
- 輸入：
n=2, k=3,?z=[1.0, 2.0] - 輸出：
0.66 - 解釋：每段長度為 0.66 時，可切割出
1+3=4段，滿足條件；每段長度為 0.67 時，可切割出1+2=3段，滿足條件，但 0.67 不是最大可行長度，最大可行長度為 0.666...，截斷后為 0.66。
- 輸入：
總結
這段代碼通過二分查找高效地解決了材料切割的最大化最小值問題，關鍵在于合理設計判斷函數ch和精確控制二分查找的邊界與精度。代碼結構清晰，算法效率高，適用于處理大規模數據。在實際應用中，可以根據具體需求進行進一步優化和擴展，如添加輸入驗證、處理無解情況等，以提高代碼的健壯性和實用性。
完結撒花hi?(。???。)??
對了
聽說給點贊+關注+收藏的人會發大財哦(oﾟ▽ﾟ)o ?
