Greatest Number
Description
Saya likes math, because she think math can make her cleverer.One day, Kudo invited a very simple game:Given N integers, then the players choose no more than four integers from them (can be repeated) and add them together. Finally, the one whose sum is the largest wins the game. It seems very simple, but there is one more condition: the sum shouldn’t larger than a number M.Saya is very interest in this game. She says that since the number of integers is finite, we can enumerate all the selecting and find the largest sum. Saya calls the largest sum Greatest Number (GN). After reflecting for a while, Saya declares that she found the GN and shows her answer.Kudo wants to know whether Saya’s answer is the best, so she comes to you for help. Can you help her to compute the GN?
Input
The input consists of several test cases.The first line of input in each test case contains two integers N (0<n≤1000) and="" m(0<m≤="" 1000000000),="" which="" represent="" the="" number="" of="" integers="" upper="" bound.Each of the next N lines contains the integers. (Not larger than 1000000000)The last case is followed by a line containing two zeros.
Output
For each case, print the case number (1, 2 …) and the GN.Your output format should imitate the sample output. Print a blank line after each test case.
Sample Input
2 1010020 0
Sample Output
Case 1: 8
继续省赛题，被这个题坑了。。。。。。题目大意：用最多四个数（也可以一个数用4次）组成一个不大于m的数，也可以相等。题目中需要注意一些小细节。
一开始想暴搜的，但是肯定超时！还是问了一下度娘。先枚举所有的两个数之和，然后4个数值和就变成了两个数之和，，然后用二分法查找最优解，不然超时。贴代码：
#include<cstdio>#include<algorithm>using namespace std;int g[1000010],f[1000010];int main(){int n,m,kase=0;while(scanf("%d%d",&n,&m),n||m){f[0]=0;int sum=0,ka=0;for(int i=1;i<=n;i++)scanf("%d",&f[i]);sort(f,f+n+1);for(int i=0;i<=n;i++)for(int j=i;j<=n;j++)if(f[i]+f[j]<=m)g[ka++]=f[i]+f[j];sort(g,g+ka);for(int i=0;i<ka;i++){int low=i,high=ka-1;while(low<high){int mid=(low+high)/2;if(g[i]+g[mid]<=m)low=mid+1;else high=mid-1;}if(g[i]+g[low]>sum&&g[i]+g[low]<=m)sum=g[i]+g[low];}if(kase) printf("\n");printf("Case %d: %d\n",++kase,sum);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
获致幸福的不二法门是珍视你所拥有的遗忘你所没有的
