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

SRM 544 Div2 Medium BoardSplitting

問題

ある建設会社はdesiredLengthの材木を材木会社に発注した.材木会社はミスをしてactualLengthの材木を納品してしまった.再発注する時間もないので,発注ミスした材木を切り貼りしてdesiredLengthの材木をdesiredCount個作ることにした.可能な限り使う材木を少なく,また切る回数を少なくした場合最小の切る回数を答えよ.

解答

actualLengthの材木からdesiredLengthを切り出すことを考える.
actualLengthの材木の残りがdesiredLengthと一致する場合切る必要はない.
残りがdesiredLength未満なら,desiredLength以上になるようにactualLengthを付け足す.

class BoardSplitting
{
public:
  int minimumCuts(int desiredLength, int desiredCount, int actualLength)
    {
      int res = 0;
      int remain = 0;
      while (desiredCount > 0){
        while (remain < desiredLength) remain += actualLength;
        remain -= desiredLength;
        desiredCount--;
        if (remain) res++;
      }
      return res;
    }
};