2010年11月9日火曜日

TopCoder 練習 Badgers(SRM 476 Div1 Easy)

Badgers(SRM 476 Div1 Easy)

■問題
まなお君は穴熊を飼うためペットショップにやって来た.ペットショップにはN匹の穴熊がいる.それぞれの穴熊は,hunger[i]だけの餌を一日に食べるが,他の穴熊が餌を食べているのを見てしまうと,更にgreed[i]だけの餌を欲しがる.まなお君は一日にtotalFoodだけの餌しかやることが出来ない.まなお君は最大に何匹の穴熊を育てることが出来るか.

■解法
仮にi匹を飼うとすると,
穴熊kは,
hunger[k]+(i-1)greed[k]
だけの餌を欲しがる.よって,上の値をN匹全てに計算しソートすることで,i匹飼うことが出来るかどうか判定することが出来る.
Nは高々50までなので,i=1,…,Nについて逐一判定すればOK.

import java.lang.*;
import java.util.*;

public class Badgers{
public int feedMost(int[] hunger, int[] greed, int totalFood){
int n=hunger.length;
int ret=0;
int[] a=new int[n];
for(int i=1;i<=n;i++){
for(int k=0;k<n;k++){
a[k]=hunger[k]+(i-1)*greed[k];
}
Arrays.sort(a);
//System.out.println(i+":"+Arrays.toString(a));
int tot=0;
for(int k=0;k<i;k++){
tot+=a[k];
}
//System.out.println("tot:"+tot);
if(tot<=totalFood){
ret=i;
}
}
return ret;
}
}

0 件のコメント: