银行贷款
题目描述
当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。
输入格式
三个用空格隔开的正整数。
第一个整数表示贷款的原值 \(w_0\)，第二个整数表示每月支付的分期付款金额 \(w\)，第三个整数表示分期付款还清贷款所需的总月数 \(m\)。
输出格式
一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 \(0.1\%\)。
样例 #1
样例输入 #1
1000 100 12
样例输出 #1
2.9
提示
数据保证，\(1 \leq w_0, w\leq 2^{31}-1\)，\(1 \leq m\leq 3000\)。
解析&代码
题目大意
给出\(n,m,k\)，求贷款者向银行支付的利率\(p\),使得:
\[\sum_{i=1}^{k}\dfrac{m}{(1+p)^i}=n \]按百分比形输出，精确到小数点后一位。
解析
\(\text{orz}\)，光是理解题意就理解了半天……果然语文差学\(\text{OI}\)也很难受。
题目中提到了一句很重要的话：利率按月累计。这是什么意思呢？这是指，假如第一个月的利率为\((1+p)\)，那么第二个月就变成了\((1+p)^2\)了。那么这两个月，你偿还的金额实际相当于你借得的\(\frac{m}{1+p}+\frac{m}{(1+p)^2}\)元。我们已知一共借了\(n\)元，那么就能得到上面提到的公式了。
关于如何计算\(m\)。首先，根据生活常识利率越大你实际偿还的金额（即你借到的\(n\)元）越小。我们对上式移项：
\[\sum_{i=1}^{k}\dfrac{1}{(1+p)^i}=\dfrac{n}{m} \]当\(p\)小于正确答案时，左式就会小于右式。反之左式就会大于右式。因此我们可以根据\(p\)的单调性倍增。
我们设\(f(p)=\text{左式}=\sum\limits_{i=1}^{k}\frac{1}{(1+p)^i}\)。设当前答案为\(p\),倍增量为\(k\)。那么如果\(f(p)<\frac{n}{m}\)，我们就可以让\(p\)加上\(k\),同时将\(\bold k\)翻倍。否则将\(k\)减半。当\(k\)小于某个阈值（即精度）时，此时的\(p\)就是答案。
倍增算法有一个好处是，你几乎不用考虑上界（即使银行放超高利贷\(\text{orz}\)）。并且精度非常容易控制：你只需要将\(p\)和\(k\)初始为非常小的数(比如\(10^{-6}\))，然后退出条件为\(k\)是否大于\(10^{-11}\)即可。
倍增的复杂度与二分相同，为\(\mathcal O(K \log N)\)。其中\(N\)为答案除以精度，\(K\)为分期付款总天数。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
double a,b,c;
cin >> a >> b >> c;
//l和r分别表示利率的最小值和最大值，也就是初始范围。
double l=0, r=1000,mid=0;
//double数据类型，相差小于0.0001结束循环，避免多次循环
while(l<r-0.0001)
{
mid=(l+r)/2;//mid为范围的中间值。
double w=a;//w为未还的总钱数。
for(int i=0;i<c;i++)//模拟还钱过程。
{
w=w-b+w*(mid/100);
}
if(w>0.0001)//检验在这个利率下，是否将钱还完。
{
r=mid;//钱未还完，利率偏大，将范围最大值设置为中间值。
}
else{
l=mid;//钱还多了，利率偏小，将范围最小值设置为中间值。
}
}
cout << fixed << setprecision(1) << round(l*10)/10;
return 0;
}