TopCoder SRM605: AlienAndHamburgers
美味しいものから順に食べる。
ただし美味しさがマイナスかつ、すでにその種類のものを食べたことがある場合は食べない。
この工程での満足度の最大値を求めれば良い。
public class AlienAndHamburgers { public int getNumber(int[] types, int[] tastes) { int ans = 0; var bambargers = types.Zip(tastes, (type, taste) => new Tuple<int, int>(taste, type)).ToArray(); Array.Sort(bambargers); Array.Reverse(bambargers); var used = new HashSet<int>(); int sum = 0; foreach (var item in bambargers) { int taste = item.Item1; int type = item.Item2; if (taste < 0 && used.Contains(type)) continue; sum += taste; used.Add(type); ans = Math.Max(ans, sum * used.Count); } return ans; } }