トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.5 数字のブロック
■■■問題■■■
Ellenは数字のブロックで遊ぼうとしている。
数字が書かれているブロックはそれぞれ高さ1で幅はWi である。
それらのブロックを高さ1,幅Lの大きな箱の中に入れる。
Ellenは大きな箱にどれだけブロックがたくさん入るか気になったが。
組み合わせがたくさんあって大変なことに気づいて、すぐに夜になってしまいそうである。
あなたは、代わりに大きな箱に最大何個のブロックが入るかを求めてください。
■■■入力■■■
L
N
W1 W2 W3 ・・・ WN
1行目は幅を表すL (1 <= L <= 10000)が与えられます。
2行目は、ブロックの数を表すN(1 <= N <= 10000)
3行目は、各ブロックの幅を表すWi(1 <= Wi <= L )が半角スペース区切りで与えられます。
■■■出力■■■
求めた数値を返してください。末尾に改行を付けてください。
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "Input1";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("16");
WillReturn.Add("3");
WillReturn.Add("10 5 7");
//2
//幅16の箱には全部は入れられないが最大2個までは入れられる。
}
else if (InputPattern == "Input2") {
WillReturn.Add("100");
WillReturn.Add("10");
WillReturn.Add("14 85 77 26 50 45 66 79 10 3");
//5
//14,26,45,10,3 の組み合わせで最大5個になる
//(どう組み合わせても6個以上は入らない)
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int L = int.Parse(InputList[0]);
int[] WidthArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray();
Array.Sort(WidthArr);
int AnswerCnt = 0;
int WidthSum = 0;
for (int I = 0; I <= WidthArr.GetUpperBound(0); I++) {
if (WidthSum + WidthArr[I] <= L) {
WidthSum += WidthArr[I];
AnswerCnt++;
}
else break;
}
Console.WriteLine(AnswerCnt);
}
}
解説