题目：密度不均的区间划分问题
现有区间[0,1] ，区间内存在(K-1) 个分界点s11,s21,…,sK-11 。这(K-1) 个分界点将整个区间分割成K 个等长的子区间，即对于任意的1≤k≤K ，满足sk1-sk-11=1K ，其中s01=0,sK1=1 。有一组样本不均匀地分布在区间[0,1] 内。给定每个子区间内样本密度，请重新确定(K-1) 个分界点，使得由这(K-1) 个分界点确定的K 个新的子区间内样本数量相同。例如，如图1所示，区间[0,1]内存在3个等距的分界点0.25、0.5和0.75，这3个分界点将整个区间分成4个等长的子区间，每个子区间内样本密度分别为2、1、0.5和0.5。
图 1 等距分割示例
此时，重新选择3个新的分界点0.125、0.25、0.5（如图2所示），由这3个分界点可将整个区间分成4个新的子区间，且满足每个子区间内样本数量占比均为1/4 。
图 2 等量分割示例
输入样例：
3（分界点的个数）
0.25 0. 5 0.75（分界点位置）
2 1 0.5 0.5（区间密度）
输出样例：
0.125 0.25 0.5 （新的分界点位置）
代码示例👇
//author:Mitchell_Donovan
//date:4.25
#include<iostream>
using namespace std;
double* run(int size, double* v, double* p);
int main() {
//数据用两个double数组来存储，v用来记录节点位置，p用来记录节点之间的密度
//其中v的大小是节点数+2（首尾各有一个边界值0或1），p的大小是节点数+1
int size1;
cout << "请输入分界点个数：";
cin >> size1;
double* v1 = new double[size1 + 2];
v1[0] = 0;
v1[size1 + 1] = 1;
cout << "请输入分界点位置：";
for (int i = 1; i <= size1; i++) {
cin >> v1[i];
}
double* p1 = new double[size1 + 1];
cout << "请输入区间密度：";
for (int i = 0; i <= size1; i++) {
cin >> p1[i];
}
double* test = run(size1, v1, p1);
for (int i = 1; i <= size1; i++) {
cout << test[i] << " ";
}
}
double* run(int size, double* v, double* p) {
//判断非法输入
if (size <= 0) {
cout << "分界点个数非法输入" << endl;
return NULL;
}
for (int i = 1; i <= size; i++) {
if (v[i] <= 0 || v[i] >= 1) {
cout << "分界点位置非法输入" << endl;
return NULL;
}
}
for (int i = 0; i <= size; i++) {
if (p[i] <= 0) {
cout << "密度非法输入" << endl;
return NULL;
}
}
//计算总数量total，则每一区间的平均数量就是total/(size+1)
double total = 0;
for (int i = 0; i <= size; i++) {
total += p[i] / (size + 1);
}
//定义并初始化储存计算结果结果的double数组out
double* out = new double[size + 2];
for (int i = 0; i < size + 1; i++) {
out[i] = 0;
}
out[size + 1] = 1;
//变量left用于记录上一部分剩下的面积
double left = 0;
//变量pos用于记录新区间的长度
double pos = 0;
//变量j用于记录原划分的情况
int j = 1;
//for循环为out数组逐个赋值
//注意for循环里的i是针对out数组的下标，原节点位置数组的下标用j来操作
for (int i = 1; i <= size; i++) {
//每一次循环会先判断left的数量是否足够，对不够和刚好以及足够三种情况分别进行运算
//left里的数量还不够
if (left < total / (size + 1)) {
pos = (total / (size + 1) - left) / p[j - 1];
//当前区域数量还不够
if (pos > (v[j] - v[j - 1])) {
left += (v[j] - v[j - 1]) * p[j - 1];
out[i] += (v[j] - v[j - 1]);
i--;
j++;
}
//当前区域数量刚刚好
else if (pos == (v[j] - v[j - 1])) {
out[i] += (out[i - 1] + pos);
left = 0;
j++;
}
//当前区域数量用完还有剩余
else {
out[i] += (out[i - 1] + pos);
left = (v[j] - v[j - 1]) * p[j - 1] - p[j - 1] * pos;
}
}
//left里的数量刚刚好
else if (left == total / (size + 1)) {
pos = (total / (size + 1)) / p[j - 1];
out[i] += (out[i - 1] + pos);
left = 0;
j++;
}
//left用完还有剩余
else {
pos = (total / (size + 1)) / p[j - 1];
out[i] += (out[i - 1] + pos);
left -= p[j - 1] * pos;
}
}
//判断最后一个区域是否满足条件
if ((out[size + 1] - out[size]) * p[size] == total / (size + 1)) {
cout << "成功" << endl;
return out;
}
else {
cout << "失败" << endl;
return NULL;
}
}输出示例👇
