【算法题】高手来。。。。。

【算法题】高手来。。。。。

你所谓的"群举法"还真没有听过,不知道是什么时间复杂度的算法呢?
这题最好说一下数据规模,这组数有多大.
我初步想法是,可以用二分答案:
先统计最大两个数的和Ma和最小两个数的和Mi,然后二分假定答案Ans进行检验.
具体检验方式是,从最大数开始枚举每个数字p(直到该数字小于Ans/2),然后计算出q=Ans-p,在所有比Ans小的数字中再使用二分查找搜索q是否存在.
如此一来复杂度是(n*logn*logm),m为最大数字对和.比n^2的穷举好.

对于你的题目要求有几点还是没弄清楚：1.你的两组数有个数限制吗？因为看你补充里居然是1 2和3，那也就是说每组数的个数是不限的，假定有一组数1,2,3,4,10。那最大的两组是1,2,3,4和10。是这样的吗？2.数字可以重复使用吗？比如有一组数1,2,3,4,6。那两组组可以是1,2,3,4和4,6吗？
另外，我想还是应该用穷举法。因为你输入的数据是没规律的，而且可能出现没有满足条件的，所以不用穷举法很难确保不会造成遗漏。追问1、是
2、不可以重复使用

为什么系统自己把答案选了。。。。！！！！追答那不是答案，只是系统给你推荐的。

有怎么复杂吗？
2个for循环就搞定了

我学C++

思路：1.把4个数放进一个数数组。遍历数组所能组成的组合（2个for镶嵌）。
2.遍历数组的同时比较大小。比较(这里比较应该是3种情况 大于MAX 或小于MIX 或等于他们)出来的数分别存入MAX和MIX（最大最小值）。同时把其组合存入个2维数组(分别要最大值和最小值的数组)。如果大于MAX 或小于MIX 把数组清空存入新组合.如果等于MAX或小于MIX就继续存入数组.

结论：这方法可以计算一组数（任意个数）的组合。同时从中找出的是所有符合条件的组合。可能少于2种也可能多于2种.
如果要程序可以写给你

我暂时保留我的看法！

二分答案显然不行吧
比如说存在两组数和都为10，那么就一定存在两组数和都为9了？
我也没什么特别好的算法。
大概这样
建立一个队列Q
遍历每个数，对于每个数X，先把Qi+X加入队列（也就是把Q的每个元素+X加入队列），最后把X加入队列。当然Qi+X和X加入前都要判重（队列里元素不要有重复）。
之后遍历队列，对于队列中的每个数B，判断2*B是不是在队列中，找到一个最大的符合条件的B就是答案。
判重和判断2*B是否在队列中可以hash或者map一下。

比如1 1 2 3 8那么选第一个1和第二个1不一样吧（如果一样的话把所有重复的去除即可）。
用穷举做（见谅）
遍历所有情况，把每种可能存下来，然后一个个数判断
#define V_LEN 10000
#define NUM 256
int A[NUM] = {1,1,2,3,8}, N = 6, MARK[NUM], V[V_LEN]; //V标志和为sum有几种可能
char S[V_LEN][NUM][NUM];
void fun(int k, int sum) //遍历所有情况，S存储sum对应数的选择
{
int i;
if(k==N)
{
for(i=0; i S[sum][V[sum]][i] = MARK[i];
++V[sum];
return;
}
MARK[k] = 0;
fun(k+1, sum);
MARK[k] = 1;
fun(k+1, sum+A[k]);
}
bool consistent(char *a, char *b) //判断a,b是否不冲突
{
int i;
for(i=0; i if(a[i]==1 && b[i]==1)return 0;
return 1;
}
bool judge(int sum) //判断sum是否不冲突
{
int i,j, p = 0;
for(i=0; i {
for(j=i+1; j {
if(consistent(S[sum][i], S[sum][j]))
++p;
if(p)return 1;
}
}
return 0;
}
int main()
{
int i, p, MAX;
for(i=0,MAX=0; i MAX += A[i];

memset(V, 0, V_LEN);
fun(0, 0);
for(i=0,p=-1; i if(judge(i) && p printf("%d", p);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！