読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM492 Div2 Easy

問題の分析
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;
    }
}