洛谷 P1163"银行贷款"（二分）

题解：

　　二分月利率，假设当前判断的月利率为x；

　　那么如何判断x是大了还是小了呢？

　　下面来分析一下Check()函数；

 1 bool Check(double x)
 2 {
 3     double tot=a;
 4     for(int i=1;i <= c;++i)
 5     {
 6         tot += tot*x;
 7         tot -= b;
 8     }
 9     return tot <= 0 ? true:false;
10 }

　　变量a,b,c分别表示题目输入的三个变量；

　　首先看第4行的for()，由题意得他是分 c 个月还完的，所以当然要循环 c 次了；

　　并且知道了月利率为 x ；

　　那么对于第 1 个月，他欠银行 a+a*x ，但由题意得，他每个月向银行还 b 元钱，所以下个月前还欠银行 a+a*x-b；

　　来到第 2 个月，欠银行 (a+a*x-b)+(a+a*x-b)*x ，还款 b 元，以此类推，直到第 c 个月后，求出他还欠银行的钱数；

　　如果欠的钱数 ≤ 0 ，说明在月利率为 x 的情况下，每月还 b 元是可以还清的，返回 true，反之，返回 false；

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int a,b,c;
 6 
 7 bool Check(double x)
 8 {
 9     double tot=a;
10     for(int i=1;i <= c;++i)
11     {
12         tot += tot*x;
13         tot -= b;
14     }
15     return tot <= 0 ? true:false;
16 } 
17 int main()
18 {
19     while(~scanf("%d%d%d",&a,&b,&c))
20     {
21         double l=0;
22         double r=1000;
23         for(int i=1;i <= 100;++i)
24         {
25             double mid=(l+r)/2;
26             if(Check(mid/100))
27                 l=mid;
28             else
29                 r=mid;
30         }
31         printf("%.1f
",l);
32     }    
33     return 0;
34 }

View Code

注意：二分枚举的范围尽可能大；

　　按照正常情况，月利率是不会超过 100% 的，所以我以为在[0,100]内枚举就可以了，但是第四个样例wa了，改成[0,1000]枚举才过的；