Greatest Number
题目描述
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?
输入
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 1000000000), which represent the number of integers and the 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.
输出
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.
示例输入
2 10
100
2
0 0
示例输出
Case 1: 8
题目大意：
输入N和M，N代表下面有N个数，选择其中的1-4个数字，其和与M的差最小，且不大于M。（可重复选择同一个数字）
解题思路：
现将N个数存入a数组，在将任意两项的和也存入数组a中。此时任取a数组中的2个就组成了所有情况。（1+1=2,1+2=3,2+2=4 ；因为a[0]=0所以存在1+0=1）
查找的时候使用了二分法，来保证效率，否则超时。
Code：
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<limits.h> 5 #define MAXN 1000 6 using namespace std; 7 int a[MAXN*MAXN/2+2*MAXN+10]; 8 int main() 9 { 10 int i,j; 11 int n,m,min,resulf,times=0; 12 while (cin>>n>>m) 13 { 14 times++; 15 min=INT_MAX; 16 if (n==0&&m==0) break; 17 for (i=1; i<=n; i++) 18 scanf("%d",&a[i]); 19 int k=n+1; 20 for (i=1; i<=n; i++) 21 for (j=1; j<=i; j++) 22 a[k++]=a[i]+a[j]; 23 sort(a+1,a+k); 24 for (i=1;i<=k-1;i++) 25 { 26 if (a[i]>m) continue; 27 int *r=lower_bound(a+1,a+k,m-a[i]); 28 if (m-a[i]-(*r)==0) {resulf=m;break;} 29 if (min>m-a[i]-(*(r-1))) {min=m-a[i]-(*(r-1));resulf=a[i]+(*(r-1));} 30 } 31 printf("Case %d: %d ",times,resulf); 32 printf(" "); 33 } 34 return 0; 35 }