山東省2010年省試合Greatest Number(巧みな暴力+二分)
5223 ワード
タイトルの説明
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
しゅつりょく
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ヒント
この問題は私が主に先日似たようなことをしたばかりなので、その問題は任意の4の数と固定的な数につづられています.そこで、この問題は先にグループ化してから綴る方法があることに気づいた.この問題ができたとき、すぐにその問題を思い出した.そこで基本的な思考の方向があります.しかし、問題はその問題が小さいので、この問題を作るには多くの問題を解決しなければならない.しかし、最終的な方法も二点を何度も使っただけだ.
具体的には,1つの配列を定義し,それぞれ0,1個の数,およびそれぞれの2個の数の和を保持し,それぞれa,b,cであると仮定し,任意の2個の数の和を元の配列で自己加算して得ることができ,その後の2点のために配列を求めて並べ替える.そしてこの配列で自分と自分を加算します.aとaを加算して0個の数の和を得る.aとbの和は1つの数の和を得る.aとcの和は2つの数の和を得る.bとcの和は3つの数の和を得る.cとcの和は4つの数の和を得る.すると0から4までの様々な数字からなる和が見つかりました.最後はmに一番近い数を選ぶだけですが、mを超えない数を選びます.ここで配列は比較的大きいので、二分で探すべきで、二分で探す方法は遍歴で、各数がその配列に加算されるときは二分で加算して、mより小さい最大値を見つけて、それから遍歴して最終的な最大値を見つけることができます.
タイムアウトの可能性があると思っていたが、この問題のバックグラウンドテストのデータは多くなく、過ぎた.
Ps:さっきインターネットで他の人のコードを探しました.基本的にはそう过ごしていることに気づいた(もともと自分がこんな奇抜な考えを思いついたことをひそかに喜んでいた..sad..)もっといい方法があるかどうか分かりません.の
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[2000001];
int cmp(int x, int y)
{
return x < y;
}
int main()
{
int n, m, i, j, mid, l, h, k, max1, x, num=0, g, r, z;
while(scanf("%d%d",&n,&m)!=EOF&&n)
{
k=0;
num++;
a[0]=0;
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
{
if(a[i]>m)
{
i--;
n--;
}
}
}
k=n+1;
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)
{
if(a[i]+a[j]<=m)
{
a[k++]=a[i]+a[j];
}
}
}
sort(a,a+k,cmp);
r=k-1;
g=k-1;
max1=0;
for(i=0; i<k; i++)
{
z=0;
l=i;
while(l<=r)
{
mid=(l+r)/2;
x=a[i]+a[mid];
if(x>m)
r=mid-1;
else if(x==m)
{
max1=m;
z=1;
break;
}
else
{
l=mid+1;
if(max1<x)
{
g=mid;
max1=x;
}
}
}
if(z)
break;
r=g;
}
printf("Case %d: %d
",num, max1);
}
return 0;
}