题目大意：给定一些数的集合，要你求出集合中满足a+b+c=d的最大的d（每个数只能用一次）
这题有两种解法，
第一种就是对分，把a+b的和先求出来，然后再枚举d-c，枚举的时候输入按照降序搜索就好，一旦d满足条件就是最大的了，另外判断不重复存一下位置就好，时间复杂度0(n^2*logn)
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; typedef long long LL_INT;
static LL_INT input[];
static pair<LL_INT, pair<int,int>>sums[ * ]; LL_INT solve(const int, const int); bool cmp(const pair<LL_INT, pair<int, int>>&x, const pair<LL_INT, pair<int, int>>&y)
{
return x.first < y.first;
} int main(void)
{
LL_INT ans;
int num_sum, sum_comb;
while (~scanf("%d", &num_sum))
{
if (num_sum == ) break;
for (int i = ; i < num_sum; i++)
scanf("%lld", &input[i]); sort(input, input + num_sum);
sum_comb = ;
for (int i = ; i < num_sum; i++)
for (int j = i + ; j < num_sum; j++)
sums[sum_comb++] = make_pair(input[i] + input[j], make_pair(i, j)); sort(sums, sums + sum_comb);
ans = solve(num_sum, sum_comb);
if (ans != INT_MAX)
printf("%lld\n", ans);
else
printf("no solution\n");
}
return EXIT_SUCCESS;
} LL_INT solve(const int num_sum, const int sum_comb)
{
int tmp[] = { , }, pos_s, pos_up;
for (int i = num_sum - ; i >= ; i--)
{
for (int j = num_sum - ; j >= ; j--)
{
if (i == j) continue;
pos_s = lower_bound(sums, sums + sum_comb, make_pair(input[i] - input[j], make_pair(, )),cmp) - sums;
pos_up = upper_bound(sums, sums + sum_comb, make_pair(input[i] - input[j], make_pair(, )),cmp) - sums; if (sums[pos_s].first == input[i] - input[j])
{
for (int k = pos_s; k < pos_up; k++)
{
if (sums[k].second.first != i && sums[k].second.first != j
&&sums[k].second.second != i && sums[k].second.second != j)
return input[i];
}
}
}
}
return (LL_INT)INT_MAX;
}
剪枝了还是100+ms，太慢了，我不是很满意，去网上找了下果然有更快的做法
其实像这种找固定数的题目都可以用散列来做，把a+b散列就好了，说实话好久没做散列我都忘记散列的那几条挺好用的公式了（貌似用书上那种散列方法效率更高），这里我就直接用链表法解决了
参考http://www.cnblogs.com/CSU3901130321/p/4546190.html
#include <iostream>
#include <algorithm>
#include <functional>
#define MOD 1001 * 1001 using namespace std; static struct _set
{
int val, num[], next;
}memmory_pool[ * ];
static int Table[ * ], input[], tp; void Hash_To_Table(const int, const int, const int);
bool Search_Table(const int, const int, const int);
int solve(const int); int main(void)
{
int num_sum, sum_comb, ans;
while (~scanf("%d", &num_sum))
{
if (num_sum == )break;
for (int i = ; i < num_sum; i++)
scanf("%d", &input[i]);
sort(input, input + num_sum);
sum_comb = num_sum*(num_sum - ) / ; tp = ; fill(Table, Table + * , -);
for (int i = ; i < num_sum; i++)
for (int j = i + ; j < num_sum; j++)
Hash_To_Table(input[i] + input[j], i, j); ans = solve(num_sum);
if (ans != INT_MAX)
printf("%d\n", ans);
else
printf("no solution\n");
}
return EXIT_SUCCESS;
} void Hash_To_Table(const int _int_value, const int i, const int j)
{
int pos = (_int_value > ? _int_value : -_int_value) % MOD;
memmory_pool[tp].val = _int_value;
memmory_pool[tp].num[] = i;
memmory_pool[tp].num[] = j;
memmory_pool[tp].next = Table[pos];
Table[pos] = tp++;
} bool Search_Table(const int _int_value, const int i, const int j)
{
int pos = (_int_value > ? _int_value : -_int_value) % MOD;
for (int k = Table[pos]; k != -; k = memmory_pool[k].next)
{
if (memmory_pool[k].val == _int_value)
{
if (memmory_pool[k].num[] != i &&memmory_pool[k].num[] != i
&&memmory_pool[k].num[] != j &&memmory_pool[k].num[] != j)
return true;
}
}
return false;
} int solve(const int num_sum)
{
for (int i = num_sum - ; i >= ; i--)
{
for (int j = num_sum - ; j >= ; j--)
{
if (i == j)continue;
if (Search_Table(input[i] - input[j], i, j))
return input[i];
}
}
return INT_MAX;
}
散列法复杂度是O(N^2)，非常快。
（另外有人在讨论版说他用O(n^3*logn)的时间复杂度方法94ms做出来了，我自己试了一下，如果他储存位置下标位置是一定会溢出的，不知道他怎么做出来的，而且就算是O(N^2*logn)的算法也是要用100+ms，我对他的做法表示怀疑）。