題目：

這題有點坑，G++過不了，C++能過。

條件：n個數(shù)據(jù)a[]，分成k段，結(jié)果精度要求兩位小數(shù)。

問題：每段最長為多少？

思路：因為精度要求為兩位小數(shù)，我先把所有的長度a[]*100。

　　　我們對答案二分搜索，把l設(shè)置為0，r設(shè)置為1000*10000*100+1（數(shù)據(jù)量每個數(shù)據(jù)最大的大小精度+1）。

　　　這樣我們搜索的數(shù)就不用處理精度了，我們可以二分算出結(jié)果然后除以100。

代碼：

#include <iostream> #include <algorithm> #include <map> #include <vector> #include <set> #include <math.h> #include <queue> #include <assert.h> #include <stdio.h> #include <stdlib.h> using namespace std; typedef long long ll; #define INF 2147483647//輸入 int n, k; double a[10010]; //返回分成k段最大的段長 double solve(ll sum) {ll l = 0, r = sum+1; //二分的左右端ll mx = 0; //保存結(jié)果while (l < r) {ll mid = (l + r) / 2;ll sum = 0; //段數(shù)求和for (int i = 0; i < n; i++) sum += a[i] / mid; //每段長mid，可以分成k段if (sum >= k) {mx = max(mx, mid); //更新答案l = mid + 1; }else {r = mid;}}return 1.0*mx/100; }int main() {cin >> n >> k;ll sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];a[i] *= 100; //將段長乘以100sum += a[i]; //對段長求和}printf("%.2lf",solve(sum));getchar(); getchar();return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1064 Cable master （二分答案，G++不过，C++就过了）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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