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;
 }
}