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．

view plainprint?

1. import java.lang.*;  
2. import java.util.*;  
3.   
4. public class Badgers{  
5.  public int feedMost(int[] hunger, int[] greed, int totalFood){  
6.   int n=hunger.length;  
7.   int ret=0;  
8.   int[] a=new int[n];  
9.   for(int i=1;i<=n;i++){  
10.    for(int k=0;k<n;k++){  
11.     a[k]=hunger[k]+(i-1)*greed[k];  
12.    }  
13.    Arrays.sort(a);  
14.    //System.out.println(i+":"+Arrays.toString(a));  
15.    int tot=0;  
16.    for(int k=0;k<i;k++){  
17.     tot+=a[k];  
18.    }  
19.    //System.out.println("tot:"+tot);  
20.    if(tot<=totalFood){  
21.     ret=i;  
22.    }  
23.   }  
24.   return ret;  
25.  }  
26. }  

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