UVA 11881 Internal Rate of Return（数学+二分）

In finance, Internal Rate of Return (IRR) is the discount rate of an investment when NPV equals zero. Formally, given T, CF, CF, ..., CF, then IRR is the solution to the following equation:

NPV = CF +  +  + K +  = 0

Your task is to find all valid IRRs. In this problem, the initial cash-flow CF < 0, while other cash-flows are all positive (CF > 0 for all i = 1, 2,...).

Important: IRR can be negative, but it must be satisfied that IRR > - 1.

Input

There will be at most 25 test cases. Each test case contains two lines. The first line contains a single integer T ( 1T10), the number of positive cash-flows. The second line contains T + 1 integers: CF, CF,CF, ..., CF, where CF < 0, 0 < CF < 10000 ( i = 1, 2,..., T). The input terminates by T = 0.

Output

For each test case, print a single line, containing the value of IRR, rounded to two decimal points. If noIRR exists, print ``No" (without quotes); if there are multiple IRRs, print ``Too many"(without quotes).

题目大意：给出CF[0]<0，CF[i]>0，i>0，求IRR（IRR>-1）令NPV = 0.

思路：设f(IRR) = NPV，这就变成了一个函数，稍微观察一下，可以发现当IRR∈(-1, +∞)的时候是单调递减的（好像是吧做完忘了），这样我们就可以二分答案0点了。当IRR无限接近-1的时候，f(IRR)→+∞（好像是吧），当IRR→+∞时，f(IRR)→CF[0]<0，令left = -1、right = 1e5（我也不知道该取什么我随便取的然后AC了），随便二分一下就好。

PS：恩？说完了？那什么时候输出No和Too many啊？关于这个坑爹的问题，看完前面的分析，笔者完全不知道什么时候会出现这两个答案，于是妥妥地没将这两个东西写进代码然后AC了。这里还有一个小技巧，题目的样例完全没有出现No和Too many这两种答案，很可能说明这两种答案都是不存在的。比如很多的题目说如果什么什么得不到答案就输出-1那样，它的样例大多都会有一个是输出-1的，当然这不是绝对的……

代码（15MS）：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 using namespace std;

 const int MAXN = ;

 const double EPS = 1e-;

 inline int sgn(double x) {

     if(fabs(x) < EPS) return ;

     return x >  ?  : -;

 }

 int CF[MAXN];

 int T;

 double f(double IRR) {

     double ret = CF[], tmp =  + IRR;

     for(int i = ; i <= T; ++i) {

         ret += CF[i] / tmp;

         tmp = tmp * ( + IRR);

     }

     return ret;

 }

 double solve() {

     double ans = -;

     double L = -, R = 1e5;

     while(R - L > EPS) {

         double mid = (R + L) / ;

         if(sgn(f(mid)) == ) L = mid;

         else R = mid;

     }

     return ans = L;

 }

 int main() {

     while(scanf("%d", &T) != EOF) {

         if(T == ) break;

         for(int i = ; i <= T; ++i) scanf("%d", &CF[i]);

         //double t; while(cin>>t) cout<<f(t)<<endl;

         printf("%.2f\n", solve());

     }

 }