本文主要是介绍poj1064 Cable master史上最详细!! 你肯定没见过这样的解题的...精度+二分 （模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
(不用精度!直接扩大 我真是太制杖了_(:з」∠)_)
/*
其实就是个用二分找答案的，但是涉及到精度问题。
因为要保留两位小数嘛，而我直接扩大了100倍.....读入的时候有点小错，然后sum记录的话会溢出，直接用maxn（出现的最大值/ 100000000（出现的最大值*100）就可以了）
不知是不是vs的原因，会有误差，就是读入的时候2.00读入成1.999999这样的，加个esp就可以了
但是输出的时候还是有点小麻烦，精简了一下，个十百分别输出就可以了。୧(๑•̀◡•́๑)૭
（pS:不这样的话，取到%100之后输出，考虑00的情况、01的情况（十位是0啊），10的情况其实没事_(:з」∠)_就按样子就好了）
另，附上抽特王永远也不会错的二分代码（至于是前面可行还是后面可行，还是要看具体问题分析，但是只要改一下下l/r就可以了）
还有，这份是团代会打的……错误百出啊。
【变量名一定要好好搞懂。】错在哪你都发现不了，二分本身没问题，是你有问题啊.……
再比如，只要判断sum能不能满足那个除数就好了，不用挨个判断，最后加起来一遍就完了呀wanle
竟然是sum溢出又错的，ll能过改别的也能过，……
daloa们说，
（网址 https://blog.csdn.net/vmurder/article/details/44347241
https://blog.csdn.net/R1986799047/article/details/50446010
https://cn.vjudge.net/status/#un=trote_w&OJId=POJ&probNum=1064&res=0&language=&onlyFollowee=false）
18-5-14
*/
模板 不用比+1..
while (l <= r) { int mid = (l + r )/ 2;if (cmp(mid)==true){l = mid + 1;ans = mid;}else r = mid - 1;}cout<<ans<<endl;//输出 的是ans!题目链接https://cn.vjudge.net/problem/POJ-1064
====更新 5.15 抽特王的代码(?) 和一些重要知识点
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
double a[10005];
//int b[10005];
int x; int piece;
const double eps = 1e-12;
//10 -12 ........
bool cmp(double ans) {int cnt = 0;bool flag = true;for (int i = 0; i < x; i++)cnt += (a[i] / ans);if (cnt >= piece)flag = true;else if (cnt < piece)flag = false;return flag;
}int main() {cin >> x >> piece;double sum = 0;for (int i = 0; i < x; i++){cin >> a[i];// aaaaa >> c >> a2;//a[i] = aaaaa * 100 + a2;a[i] += eps;sum += a[i];}double l = 0;double r = sum;double ans = 0;for (int i = 1; i <= 100;i++) {double mid = (l + r) / 2;if (cmp(mid) == true){l = mid ;}else r = mid;}printf("%.2f\n", floor(100 * l) / 100);
// cout << floor(ans*100)/100 << endl;//2.045 2.04 204.5 地板了 向下取整 .... 四舍五入return 0;
}
01
计组怎么学的.....2.00读进来没事 2.50没事 2.05就会有精度损失到2.049999
那就加个esp..问题是怎么加!
是这样的!!!
const double eps = 1e-12;这个是10的负12次方,然后加上他就会把精度损失减小了...因为 在int范围内嘛
还有就是要写成double啊
02
二分100次是因为时间限度嘛,就像取极限的时候无限接近但是不会到达，所以你在double哪里l<=r就不行了啊这怎么可以随便分,,,所以就100次就好了
那个万能模板是实数范围内的-.-具体的看代码
03
floor是地板,向下取整，那么那么2.545这样的我们不想四舍五入啊，就先变成254 后面5没了 再除了嘛QAQ（）
竟然过了0.0
*/
这么简单一个题 真tm难得_(:з」∠)_....
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<vector>
using namespace std;
int a[10005];
//int b[10005];
int x; int piece;
bool cmp(int ans) {int cnt = 0;bool flag = true;for (int i = 0; i < x; i++){cnt += (a[i] / ans);if (a[i] % ans < piece)flag = false;//return false;}if (cnt >= piece)flag = true;//return true;//这样产生的误差我们可以忽略不计//改判定... else if (cnt < piece)flag = false;if (flag == false)return false;return true;
}//【怎么保留两位小数啊？】int main() {cin >> x >> piece;int sum = 0.0;int aaaaa; int a2; char c;int re = 0;for (int i = 0; i < x; i++){cin >> aaaaa >> c >> a2;a[i] = aaaaa * 100 + a2;// re = max(a[i], re);}int l = 1;int r = 100000000;// re;//sum;int ans = 0;while (l <= r) {int mid = (l + r) / 2;if (cmp(mid) == true){l = mid + 1;ans = mid;}else r = mid - 1;}int temp = ans % 100;cout << ans / 100 << "." << temp / 10 << temp % 10 << endl;return 0;
}这篇关于poj1064 Cable master史上最详细!! 你肯定没见过这样的解题的...精度+二分 （模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
