本文主要是介绍sdnu山东省ACM 2010年第一届省赛Greatest Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：http://210.44.14.31/problem/show/1141
注意事项：
范围太大，爆搜超时。
本人猜测，本题的测试数据可能均是需要四个数才能的出最优解（依据第二个代码）。
具体分析看代码。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio> //别用cin，本题测试数据较多
using namespace std;
int num[1000000 + 10];
int main()
{int n, m;int k = 0; while (scanf_s("%d%d",&n,&m)&&(n||m)){num[0] = 0;int max = 0;for (int i = 1; i <= n; i++){scanf_s("%d", &num[i]);if (num[i]>m) //超范围的直接去除{n--;i--;continue;}} //此时num数组里有 1到n 个单个的值int cnt = n+1;cout << "Case " << ++k << ": ";for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)if (num[i] + num[j]<=m)num[cnt++] = num[i] + num[j]; //此时前n个位单个值，n+1到cnt为不大于m的所有两个值的和sort(num, num + cnt);int left, right=cnt-1,nextright=cnt-1;for (int i = 0; i < cnt; i++) //因为数组里有单个值也有两个值的和 所以会出现 两个值的和、三个值的和、四个值的和{left = i;while (left <= right){int mid = (left + right) >> 1;int tempmax = num[i] + num[mid];if ( tempmax< m){left = mid + 1;if ( tempmax> max){max = tempmax;nextright = mid; //关键：在已经排好序的数组里，从i到i+1 i对应的mid必定在i+1对应的mid 的右边即mid（i）>=mid（i+1）这样做可以提高效率}}else if (tempmax>m)right = mid - 1;else //找到直接结束循环{max = m;i = cnt;break;}}right = nextright; //将right减小}cout << max << endl<<endl;}return 0;
}附另解（本解法只用了四个数的组合便可ac，代码简单就不做详解了）：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;int str[1000010],op[1010];
int main()
{int i,j,k,n,m,ans,t=1;bool flag=false;while(~scanf("%d%d",&n,&m),n||m){op[0] = k = 0;for(i=1;i<=n;i++)scanf("%d",&op[i]);sort(op,op+n+1);for(i=0;i<=n;i++)for(j=i;j<=n;j++){if(op[i]+op[j]<=m)str[k++] = op[i]+op[j];}sort(str,str+k);ans = 0;for(i=0;i<k;i++){int low=i,high=k-1;while(low<high){int mid=(low+high)/2;if(str[i]+str[mid]>m)high = mid-1;elselow = mid+1;}if(str[i]+str[low]>ans && str[i]+str[low]<=m)ans = str[i]+str[low];}if(flag)printf("\n");printf("Case %d: %d\n",t++,ans);flag = true;}return 0;
}
这篇关于sdnu山东省ACM 2010年第一届省赛Greatest Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
