求C算法,排列组合问题。

发布网友 发布时间：2022-11-18 15:00

我来回答

共6个回答

热心网友 时间：2024-10-08 20:31

先对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个差值数，） 未完待续

热心网友 时间：2024-10-08 20:31

#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],
计算
abs(id[i] - y[left])
abs(id[i] - y[right])
取两者小的放入累加器
}
如果为0，i=i+1,做下一个循环

注意一下，
有的点没有id[left]，
有的点没有id[right]。
处理一下即可。（用 y[right], 或用 y[left])

热心网友 时间：2024-10-08 20:32

感觉这个题目有点怪，不知道是不是你的描述有问题：
每一次计算剩下的（M-N）个数离最近的参考点的差值（小于0取绝对值）的和，结果只有一个值，无所谓最小值；
如果球所有组合情况下和的最小值，也就不存在随机的问题，因为最小值只存才与特定的情况下的。
如果是第二种情况，先排序，再逐差，给差值排序，在根据差值中M-N个最小的数来抽N个参考点，如果不清楚，我明天可以尝试做个程序。
可以给我留言。

热心网友 时间：2024-10-08 20:32

我大概想了一下， 这个问题有点难

常规的穷举， 时间上肯定过不去， 估计效率为 O(m!)

这是相当低下的

有一种办法是 随机*近， 采用多次随机来取其中最小值

这样至少可以把时间控制到可以忍受的范围之内

答*度上不会太好， 但次随机次数越多越接近

终极的算法可能是dp, 但我并没有想到合适的状态转移

这种难题可以问问算法高手们，特别是那些 noi ioi选手

热心网友 时间：2024-10-08 20:33

有点复杂，不过排序可以用一下结构体快排，找出最小值

热心网友 时间：2024-10-08 20:34

用两个数组a,b分别存M，N个数，再用剩下的数依次和数组a里的数比较求绝对值最小值再累加