简介
采用鸽笼原理;可以达到O(1);
code
#include<stdio.h>
#include <iostream>
#include <vector>
using namespace std;
typedef struct BLOCK {
int blockNumber;
double min;
double max;
BLOCK(int _blockNumber=0, double _min=1000, double _max=-1000) {
min = _min;
max = _max;
blockNumber = _blockNumber;
}
};
int main() {
int n;
cin >> n;
vector<double> num(n);
double min = 1000; double max = -1000;
for (int i = 0; i < n; i++) {
cin >> num[i];
if (num[i] > max) {
max = num[i];
}
if (num[i] < min) {
min = num[i];
}
}
vector<BLOCK> b(n - 1);
double gap = (max - min) / (n - 1);
//只选择去掉最大值进行 投球
for (int i = 0; i < n; i++) {
if (num[i] == max ) {
continue;
}
int index = (n - 1)*(num[i] - min) / (max - min);
b[index].blockNumber++;
if (b[index].max < num[i]) {
b[index].max = num[i];
}
if (b[index].min > num[i]) {
b[index].min = num[i];
}
}
// max分开处理
b[n - 2].blockNumber++;
if (b[n - 2].max < max) {
b[n - 2].max = max;
}
if (b[n - 2].min > max) {
b[n - 2].min = max;
}
double maxGap = 0;
for (int i = 0; i < n - 2; i++) {
if (b[i].max - b[i].min > maxGap) {
maxGap = b[i].max - b[i].min;
}
double lastMax = b[i].max;
while (b[i + 1].blockNumber == 0) {
if (i + 1 == n - 1) {
break;
}
i++;
}
if (b[i+1].min - lastMax > maxGap) {
maxGap = b[i+1].min - lastMax;
}
}
cout << maxGap << std::endl;
system("pause");
return 0;
}
测试样本
5 2.3 3.1 7.5 1.5 6.3
输出
3.2