Last active
August 29, 2015 14:05
-
-
Save kazurof/4865fa5ab62c8aae09af to your computer and use it in GitHub Desktop.
sample code for https://paiza.jp/poh/kirishima
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Scanner; | |
public class Main { | |
/** | |
* 添字人数になるように会社を選んだ組み合わせの時の総コスト。 | |
* {@link #NOT_ASSIGNED} の場合はそのような組み合わせは存在しない。 | |
*/ | |
static int[] costByNumOfMember; | |
/** | |
* {@link #costByNumOfMember} において、 | |
* そのような人数に対する会社の組み合わせは存在しないことを表現する。 | |
*/ | |
static final int NOT_ASSIGNED = -1; | |
/** 全ての会社を選択した場合の人数 */ | |
static int numOfMemberIfUseAll; | |
/** 必要な人数 */ | |
static int requiedNumOfMember; | |
/** 会社の数 */ | |
static int numOfCompany; | |
public static void main(String[] args) { | |
List<Company> companyList = new ArrayList<Company>(); | |
// 入力データの読み込み。 | |
try (Scanner scanner = new Scanner(System.in)) { | |
requiedNumOfMember = scanner.nextInt(); | |
numOfCompany = scanner.nextInt(); | |
for (int i = 0; i < numOfCompany; i++) { | |
Company company = new Company(scanner.nextInt(), scanner.nextInt()); | |
companyList.add(company); | |
numOfMemberIfUseAll += company.members; | |
} | |
}; | |
costByNumOfMember = new int[numOfMemberIfUseAll + 1]; | |
for (int i = 0; i <= numOfMemberIfUseAll; i++) { | |
costByNumOfMember[i] = NOT_ASSIGNED; | |
} | |
// それぞれの会社毎に処理 | |
for (Company company : companyList) { | |
for (int i = numOfMemberIfUseAll; company.members < i; i--) { | |
int costWithoutThisCompany = costByNumOfMember[i - company.members]; | |
if (0 < costWithoutThisCompany) { | |
updateCostByNumOfMember(costWithoutThisCompany + company.cost, i); | |
} | |
} | |
// この会社のみを利用することを検討する必要がある場合 | |
updateCostByNumOfMember(company.cost, company.members); | |
} | |
// 結果の検索と表示 | |
int result = -1; | |
for (int i = requiedNumOfMember; i <= numOfMemberIfUseAll; i++) { | |
if (result < 0 || | |
(costByNumOfMember[i] >= 0 && result > costByNumOfMember[i])) { | |
result = costByNumOfMember[i]; | |
} | |
} | |
System.out.println(result); | |
} | |
static void updateCostByNumOfMember(int newCost, int members) { | |
if (costByNumOfMember[members] == NOT_ASSIGNED | |
|| newCost < costByNumOfMember[members]) { | |
costByNumOfMember[members] = newCost; | |
} | |
} | |
} | |
class Company { | |
Company(int members, int cost) { | |
this.members = members; | |
this.cost = cost; | |
} | |
int members; | |
int cost; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment