- //
- //<<最接近神的地方>>
- //
- //题目:有两个数组a,b,大小都为n,数组元素的值任意,无序;
- //要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小
- //
- //version 1
- //累加拼接后的新数组的元素之和,然后除以2得到下平均值
- //从新数组中取一个值,默认就是第一个元素的值作为基值
- //剩下的c-1个元素就通过穷举来组合的,然后求出与平均值最近组合的元素数组
- //该题目有一个规律:最后生成的两个数组肯定是一个在平均值左边,一个在平均值右边,或者两个相等;那么这两个最终的数组与平均值的距离相等的,
- //也就说如果在左边找到一个组合之和离平均值最近的,那么剩下的元素之和必定在平均值右边离平均值最近,也就是大于平均值的和值中最小的一个
- #include "stdafx.h"
- #include <algorithm>
- #include <iostream>
- #include <stdlib.h>
- using namespace std;
- int avg=0;
- int lastvalue=0;
- int *c =new int[];
- int *output =new int[];
- void print(int *a, int len, int num, int des, int loc); //生成以某一个元素为基的所有组合,并调用get_arry函数
- void get_arry(int *a,int num); //比较元素之和与平均值的差距,取距离最近组合
- int sum(int *a,int len); //求组合元素之和,返回给get_arry函数
- int main() //预处理数组(拼接,并取出最后一个作为基值),打印数组
- {
- //int a[]={57,68,59,52,72,28,96,33,24};
- //int a[]={10,100,8900,300,792};
- //int b[]={90,900,9000,12,341};
- int a[]={1,3,2,1,7};
- int b[]={14,15,16,17,18};
- int len=sizeof(a)/sizeof(a[0]);
- c[len-1]=lastvalue=b[len-1];
- for (int d=0;d<len-1;d++)
- {
- a[d+len]=b[d];
- }
- len=2*len; //再次计算a的元素个数怎么不变,只好*2了
- avg=sum(a,len-1)/2;
- cout <<"平均值:"<<avg<<endl<<"最值组合a:";
- print(a,len-1,0,len/2-1,0); //最后一个参数代表指针从数组索引1的地方向右找起,再调用print的函数,生成所有len/2-1元素的组合
- for (int d=0;d<len/2;d++)
- {
- cout<<c[d]<<",";
- }
- //返回的组合数组再由mian函数传递给sum函数计算和,由mian函数比较与平均值的距离(绝对值),丢弃离平均值远的组合数组
- getchar();
- delete [] c;
- delete [] output;
- return 0;
- }
- int sum(int *a,int len)
- {
- int sumvalue=0;
- for (int d=0;d<len;d++)
- sumvalue+=a[d];
- sumvalue+=lastvalue;
- //cout<<endl<<"------------------------>sumvalue:"<<sumvalue<<" avg:"<<avg<<endl;
- //for (int d=0;d<len;d++)
- //{
- // cout<<a[d]<<",";
- //}
- //cout<<endl;
- return sumvalue;
- }
- void get_arry(int *a,int num)
- {
- if(c[0]==-33686019)
- {
- for (int d=0;d<num;d++)
- {
- c[d]=a[d];
- }
- }
- else
- if (abs(sum(a,num)-avg)<abs(sum(c,num)-avg))
- {
- for (int d=0;d<num;d++)
- {
- c[d]=a[d];
- }
- }
- }
- void print(int *a, int len, int num, int des, int loc)
- {
- if(num==des)
- {
- output[num] = 0;
- get_arry(output,num);
- return;
- }
- if(des-num>len-loc) //两点:1、if(还需要的元素个数>剩下的元素个数);
- return; // 2、len-loc不可能为负,所以desc-num最小也只能大于等于0,所以保证了num不会大于desc;
- // 3、所以 当剩下的元素个数不能满足时 或者 num大于desc时 就会退出本次调用(return)。
- output[num] = a[loc];
- print(a,len,num+1,des,loc+1); //每递归调一次,n就被加1,一层层的加; 然后在退出调用的时候,一层层的减。
- //每次return后回到递归调用本身的时候就相当于在退出本次调用,从哪里进从哪里出。
- print(a,len,num,des,loc+1); //可以通过不断的递归为第4个值赋loc+i的值
- }
- //该片段来自于http://www.codesnippet.cn/detail/3012201411434.html
来源: http://www.codesnippet.cn/detail/3012201411434.html