C/C++の宿題を片付けます 79代目

>>152
そのプログラムで毎回最大値最小値をとっているところをヒープまたは二分木で
管理してやれば O(n log n) になる．これは >>146 のコードと本質的には同じ．
#include <iostream>
#include <set>
using namespace std;
int main() {
  const double a[] = {6.05385, 8.52025, 15.8029, 15.2049, 10.5501, 
    11.904, 2.34999, 10.0731, 0.270519, 4.03088, 2.27745, 13.3459};
  const int n = sizeof(a)/sizeof(a[0]);
  const double h = 8.58708;
  int I = 0, J = 0;
  multiset< double, greater<double> > gS;
  multiset< double, less<double> > lS;
  for (int i = 0, j = 0; i < n; ++i) {
    gS.insert(a[i]);
    lS.insert(a[i]);
    for (; *gS.begin() - *lS.begin() > h; ++j) {
      gS.erase(gS.find(a[j]));
      lS.erase(lS.find(a[j]));
    }
    if (i - j > I - J) {
      I = i;
      J = j;
    }
  }
  cout << J << "," << I << endl;
}