SRM440 Div2 Easy

250

2分探索

view plainprint?

1. double f(vector<int> h, double g)  
2. {  
3.   double sum = 0;  
4.   for (int i = 0; i < h.size(); ++i) {  
5.     sum += sqrt(2.0 * h[i] / g);  
6.   }  
7.   return sum;  
8. }  
9.   
10. class IncredibleMachineEasy {  
11. public:  
12.   double gravitationalAcceleration(vector <int> H, int T)  
13.   {  
14.     double small = 1e-10;  
15.     double large = 1e256;  
16.   
17.     for (int loop = 10000; loop--; ) {  
18.       double mid = (small + large) / 2.0;  
19.       double t = f(H, mid);  
20.       if (t >= T) small = mid;  
21.       else large = mid;  
22.     }  
23.   
24.     return small;  
25.   }  
26. };  

double f(vector<int> h, double g)
{
  double sum = 0;
  for (int i = 0; i < h.size(); ++i) {
    sum += sqrt(2.0 * h[i] / g);
  }
  return sum;
}

class IncredibleMachineEasy {
public:
  double gravitationalAcceleration(vector <int> H, int T)
  {
    double small = 1e-10;
    double large = 1e256;

    for (int loop = 10000; loop--; ) {
      double mid = (small + large) / 2.0;
      double t = f(H, mid);
      if (t >= T) small = mid;
      else large = mid;
    }

    return small;
  }
};