問題の分析
N本のワインがあり、どれか一本を熟成させ、どれか一本を若返らせます。i番目のワインを熟成させるとprofit[i]の利益が得られ、
i番目のワインを若返らせるとdecay[i]の損失が生じます。
得られる最大の利益を求めなさい。
方針
利益の最大値−損失の最小値を返せばOKです。
但し、利益最大のワインと損失最小のワインが同じである場合は
利益の最大値−損失の2番目の最小値と利益の2番目の最大値−損失の最小値の大きい方となります。
ソースコード
using System; using System.Collections.Generic; using System.Text; public class TimeTravellingCellar { public int determineProfit(int[] profit, int[] decay) { int[] sortedP = (int[])profit.Clone(); Array.Sort(sortedP); int pmax = sortedP[sortedP.Length - 1]; int psec = sortedP[sortedP.Length - 2]; int[] sortedD = (int[])decay.Clone(); Array.Sort(sortedD); int dmin = sortedD[0]; int dsec = sortedD[1]; int idx = 0; for (int i = 0; i < profit.Length; i++) if (pmax == profit[i]) idx = i; if (decay[idx] == dmin) { return Math.Max(pmax - dsec, psec - dmin); } else return pmax - dmin; } }
ただ、問題のサイズが小さいので全通り調べることもできます。この方が簡単に実装できていいですね。
間に合うならよりNaiveな方法で解いた方がいいと思います。
using System; using System.Collections.Generic; using System.Text; public class TimeTravellingCellar { public int determineProfit(int[] profit, int[] decay) { int max = 0; for(int i = 0;i < profit.Length;i++) for(int j = 0;j < profit.Length;j++) if(i != j) max = Math.Max(max, profit[i] - decay[j]); return max; } }