// testvs2.cpp : 定义控制台应用程序的入口点。
//
#include ""
#include <unordered_map>
#include <vector>
#include <iostream>
#include <>
#include<>
#include<>
#define random(x) (rand()%x)
using namespace std;
/// 随即产生range以内的needSortNum个数字
void genarateNum(int needSortNum,vector<double> &numList)
{
for (int i = 0; i < needSortNum; i++)
{
int numObj = random(10);
numList.push_back(numObj);
}
}
/// 进行从小到大的排序
void sortNum(vector<double> &numList)
{
for(int i = 1;i < numList.size();++i)
{
for(int j = i;j > 0;--j)
{
if(numList[j] < numList[j - 1])
{
double temp = numList[j];
numList[j] = numList[j-1];
numList[j-1] = temp;
}
}
}
std::wcout << L"最大值：" << numList[numList.size() - 1] << L"最小值：" << numList[0] << std::endl;
}
/// 计算平均值
double setAverageNum(vector<double> &numList,int groupsNum)
{
double totalNum = 0;
int size = numList.size();
for (int i = 0; i < size; i++)
{
totalNum = totalNum + numList[i];
}
double averageNuma = totalNum / groupsNum;
return averageNuma;
}
/// 返回与差值比较小的index
int getSuitedIndex(double difference, std::vector<double> &cloneList)
{
int size = cloneList.size();
int reIndex = 0;
for (int i = 0; i < size; i++)
{
double currAbs = difference - cloneList[i];
if (currAbs > 0)
{
continue;
}
else
{
reIndex = i;
break;
}
}
if (reIndex == 0)
{
std::wcout << L"这样就最小了~" << std::endl;
reIndex = 0;
}
else
{
if (std::abs(difference - cloneList[reIndex - 1]) < std::abs(difference - cloneList[reIndex]))
{
reIndex = reIndex - 1;
}
}
return reIndex;
}
///将分组的数据保存到Map
void storeList2Map(std::vector<double> &tempList,int &currGroup,std::unordered_map<int, std::vector<double>> &resultMap)
{
std::vector<double> gourpList;
(gourpList.end(), (), tempList.end());
currGroup = currGroup + 1;
(std::make_pair(currGroup, gourpList));
();
}
/// 处理余下来的数据
void doTheRestNum(vector<double> cloneList,int &currGroup,std::unordered_map<int, std::vector<double>> &resultMap)
{
int size = cloneList.size();
if (size > 0)
{
std::vector<double> tempList;
for (int i = 0; i < size; i++)
{
tempList.push_back(cloneList[i]);
}
(std::make_pair((currGroup + 1), tempList));
}
}
/// 开始分组
void start2Divide(vector<double> numList,double averageNum,int groupsNum,std::unordered_map<int, std::vector<double>> &resultMap)
{
int currGroup=0;
vector<double> cloneList;
(cloneList.end(), (), numList.end());
int size = numList.size();
double groupTempNum = 0;
int currIndex = size-1;
std::vector<double> tempList;
while (cloneList.size() > 0)
{
groupTempNum = groupTempNum + cloneList[currIndex];
if (groupTempNum < averageNum)
{
tempList.push_back(cloneList[currIndex]);
(() + currIndex);
currIndex = currIndex - 1;
}
else
{
double groupNum = groupTempNum - cloneList[currIndex];
while (groupNum < averageNum)
{
double difference2 = averageNum - groupNum;
int index2 = getSuitedIndex(difference2, cloneList);
if (index2 == 0)
{
break;
}
double suitedObj2 = cloneList[index2];
tempList.push_back(cloneList[index2]);
(() + index2);
currIndex = currIndex - 1;
groupNum = groupNum + suitedObj2;
}
storeList2Map(tempList,currGroup,resultMap);
groupTempNum = 0;
}
if (currGroup == groupsNum - 1)
{
doTheRestNum(cloneList,currGroup,resultMap);
break;
}
}
}
//输出分组情况
void printAllResult(vector<double> numList,std::unordered_map<int, std::vector<double>> resultMap)
{
//输出随机产生的数
for(int i=0;i<numList.size();i++)
{
cout<<numList[i]<<" ";
}
cout<<endl<<endl;
//输出每组的分组情况及其和
auto iter = ();//auto自动识别为迭代器类型unordered_map<int,string>::iterator
while (iter!= resultMap.end())
{
double sum=0;
for(int i=0;i<iter->second.size();i++)
{
cout << iter->second[i] << " ";
sum+=iter->second[i];
}
cout<<" 其总和为： "<<sum<<endl;
++iter;
}
}
/// <summary>
/// @Description 假定needSortNum个数，分为groupsNum组
/// </summary>
void testSorted(int needSortNum,int groupsNum)
{
vector<double> numList;//原始数据
std::unordered_map<int, std::vector<double>> resultMap;//分组结果
genarateNum(needSortNum,numList);
//sortNum();//不排序，分的个数比较均匀，否则小的数容易分到一组里
double averageNum=setAverageNum(numList,groupsNum);
start2Divide(numList,averageNum,groupsNum,resultMap);
printAllResult(numList,resultMap);
}
int _tmain(int argc, _TCHAR* argv[])
{
testSorted(96,5);
return 0;
}