UC知道求C算法，排列组合问题。
来源：百度知道 编辑：UC知道 时间：2024/05/21 18:39:29
我的想法是：先对M个数排序，然后抽取N个数，再定位每个剩下点的最近参考点，求得差值后再整体求和。
感觉算法很麻烦，而且当M稍微有点大时，M抽N的组合结果会很大。
注意：N个参考点是从M个数中抽出来的，也就是说，参考点的值事先是未知的(所以我才要用到组合，穷举出所有的可能,##!)。
回：QQ_qmin
感谢你的关注！题目的意思同你所说的问题2。
注意题中问的是：求“和的最小值”。若是随机只抽取一种可能，就不存在“和得最小值”了。而我上面的算法就是为了求“和的最小值”，才通过一个个穷举出M中选N个参考点的所有情况，来算“和得最小值”。
先对M个数排序，再定位没个数距离最近的参考点的差值，对差值排序（此步骤要比M随机抽取N要节约很多时间复杂度），找出最小差值的N个点。再定位N个数（避免了从M个中抽取N个的随机组合） 。
对你的问题我有个疑问，我觉得有个歧义
1、是要随机抽取N个数一次（注意是一次），然后找到剩余的M-N个数对这N个数的最小参考差值？
2、还是抽取N个数多次（注意是多次，假如M=4，N=1，就必须抽取4次），然后分别找出每次的最小参考差值（多个，M=4，N=1的时候就是有4个最小参考差值）比较，找到最小的参考差值？
是问题1还是问题2
如果是问题1：那么只需要随机抽取一次，不论有多少种抽取可能，你都不用去管，那就是先排序，再抽N个数（只抽一次），找最小差值。
如果是问题2：那么为了避免抽取多次，需要先排序，再比较排序后的所有相邻的数的差值存入另外数组，（例如4（M=9）个数1，3，5，9 ，17，26，36，47，48。则差值为2，2，4，8，9，10，11，1存入数组，如果你要抽取的数N是1，那么最小差值一定是1，如果你要抽取的N是2，那么最小差值是1+2是3，如果你要抽取的N是3则最小差值是1+2+2=5（拿1，5，18）,这里有个需要注意的地方：不能拿差值连续的3个数字，比如你要抽取的N是4的时候你想去拿1+2+2+4是不可以的，只能抽出连续的3个数字（2，2，4）中的最大值不要换成另外的最小值，即拿1+2+2+8，这个是原因你可以自己列例子试想下（因为不太好说清楚），此处可看成一段分析结束。）继续下一段分析（当你要拿的数N > (M-1)-[(M-1)/3]的时候需的分析方法(M-1)代表M个数有多少差值，3是因为你不能拿连续的3个差值数，） 未完待续
#define M 1000
int y[M], id[M];
先对M个数排序;
然后抽取N个数;
id[M]; 里填信息，先全给0，然后做 抽到的序号元素给1。
然后对id[i] 循环检查，
如果为1，
则
{
向左找第一个id[left]为0对应的y[left],
向右找第一个id[right]为0对应的y[right