今天讲二分精确题型
目录
题目：kotori的设备
思路：
题目：银行贷款
思路：
题目：一元三次方程求解
思路：
题目：kotori的设备
思路：
求：设备最长使用时间
二分查找：对使用时间进行二分查找
二分依据：该时间可提供的能量（对比该时间需要补充的能量，若超过则增加时间找最优解）
#include <iostream>
using namespace std;
int n;
double sum,p,l=0,r=1e10;
double a[200000],b[200000];
int check(double ans){ double q=p*ans;//这个时间可提供的能量sum=0;for(int i=0;i<n;i++){if(a[i]*ans<=b[i]) continue;//设备在该时间内不需要充电sum+=(a[i]*ans-b[i]);//否则就计算还需要的额外能量}return sum<=q;//需要的能量小于等于充电器提供的，则这个时间可以做解
}
int main(){cin>>n>>p;for(int i=0;i<n;i++){cin>>a[i]>>b[i];sum+=a[i];}if(sum<=p){ //若所有设备的消耗能量速度总和还是小于充电器的充电速度，输出-1。cout<<-1.000000<<endl;return 0;}while(r-l>1e-6){ //和标准答案相差小于10e-4即可double mid=(l+r)/2;if(check(mid)) l=mid;//如果mid可以做解，就向右逼近else r=mid; //如果不能做解，就向左找解}cout<<l<<endl;
//二分精确就简单多了，r-l控制好精度，到时候就不需要管=在哪里，不需要管输出l，r，midreturn 0;
}
题目：银行贷款
思路：
题意就是在换完每月的钱后，到12月时钱恰好为pay*mon，也就是loan=loan*(1+ans)-pay经过12次循环后为0或逼近0
求：月利率
二分查找：对利率进行二分查找(二分精确)
二分依据：该利率下12个月后的贷款
#include <iostream>
#include <cstdio>
using namespace std;
int main(){int loan,pay,mon;double l=0,r=10,mid,t; //利率可能大于1cin>>loan>>pay>>mon;while(r-l>0.0001){ mid=(l+r)/2;t=loan;for(int i=0;i<mon;i++){t=t*(1+mid)-pay;}if(t>0) r=mid; //t大于0说明利率太大了，那就调小利率else if(t<0) l=mid;else{printf("%.1f",mid*100); //（找理想解）可以直接输出return 0;}}printf("%.1f",mid*100); //保留小数点后一位return 0;
}
题目：一元三次方程求解
思路：
二分查找：对解进行二分
二分依据：零点定理
#include<cstdio>
double a,b,c,d;
double f(double x) //输入自变量，返回函数值
{return a*x*x*x+b*x*x+c*x+d;
}
int main()
{double l,r,mid,x1,x2;int ans=0,i; //ans是答案个数scanf("%lf%lf%lf%lf",&a,&b,&c,&d); for (i=-100;i<100;i++){l=i; r=i+1; x1=f(l); x2=f(r); //将每个i分成[i,i+1]区间，然后处理f(i)和f(i+1)符号if(x1==0) //若i刚好命中就输出（即左端点i刚好是零点）{printf("%.2lf ",l); ans++; //不能判断右端点，会重复} if(x1*x2<0) //根落在区间时就二分查找{while(r-l>=0.001)//控制精度 {mid=(l+r)/2; if(f(mid)*f(r)<=0) l=mid; //向右压缩else r=mid; //向左压缩}printf("%.2lf ",r); //左右都可以ans++;}if (ans==3) break; }return 0;
}
