Demo entry 6742372

max_interval

   

Submitted by anonymous on May 17, 2018 at 17:25
Language: C++. Code size: 2.2 kB.

#include <iostream>
#include <fstream>
using namespace std;

//存放实数映射后的索引值的筐
typedef struct {
    int max_index;  //同一个筐中各数的最大值在data中的下标
    int min_index;  //同一个筐中各数的最小值在data中的下标
} Bucket;

int main() {
    int N = 0;          //输入实数个数
    float *data;        //存放输入的实数的数组
    Bucket *buckets;    //筐
    int max_index = 0;              //实数最大值在data中的下标
    int min_index = 0;              //实数最小值在data中的下标
    float max_interval = 0.0f;      //输出最大间隙的结果
    int left_bound = 0;             //间隙的下界
    ifstream in_file("input.txt", ios::in);
    if (in_file.is_open()) {
        in_file >> N;
        data = new float [N];           //N个实数
        buckets = new Bucket [N + 1];   //N+1个筐
        for (int i = 0; i < N; i ++) {  //输入实数,储存入data并求出最值
            in_file >> data[i];
            if (data[i] > data[max_index]) max_index = i;
            if (data[i] < data[min_index]) min_index = i;
        }
        in_file.close();
    }
    for (int i = 0; i < N + 1; i ++) { //将筐中的最值索引初始化为-1
        buckets[i].max_index = -1;
        buckets[i].min_index = -1;
    }
    for (int i = 0; i < N; i ++) {
        //将最大值与最小值之间分割为N+1个区域,将各实数映射到下标为0~N的筐中
        int index = (data[i] - data[min_index]) * N / (data[max_index] - data[min_index]);

        //若筐中无数(最值索引为-1) 或 当前实数比筐中最大值更大,则将筐中最大值设为当前实数在data中的下标i
        if (buckets[index].max_index == -1 || data[i] > data[buckets[index].max_index]) buckets[index].max_index = i;
        //若筐中无数(最值索引为-1) 或 当前实数比筐中最小值更小,则将筐中最小值设为当前实数在data中的下标i
        if (buckets[index].min_index == -1 || data[i] < data[buckets[index].min_index]) buckets[index].min_index = i;
    }
    for (int i = 1; i < N + 1; i ++) {
        if (buckets[i].max_index != -1) {
            //如果当前筐中有数,则计算当前筐中的最小值与上一个筐中的最大值的差值
            //根据大小关系,更新max_interval,并更新left_bound为当前筐的下标
            float temp_interval = data[buckets[i].min_index] - data[buckets[left_bound].max_index];
            max_interval = max(max_interval, temp_interval);
            left_bound = i;
        }
    }
    ofstream out_file("output.txt", ios::out);
    if (out_file.is_open()) {
        out_file << max_interval << endl;       //输出最大间隙值
        out_file.close();
    }
    return 0;
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).