SRM 150 DIV2 Easy(250) - WidgetRepairs

SRM 150 DIV2 Medium(500) - InterestingDigitsを解いたので、ついでにEasy問題も解いてみた。 この問題は、前日までの積み残し（rest）と当日到着分(arrivals[i]）の合計が当日処理可能分（numPerDay）を超えるかどうかを考慮すればOK。 前日までの積み残しと当日到着分の合計が当日処理可能分よりも多い場合は、積み残しが0より大きくなる。 また、前日までの積み残しと当日到着分の合計が当日処理可能分よりも小さい場合は、積み残しが0より小さくなる。この場合は、積み残しは0。 そのため、以下の式で当日の積み残しが計算可能。

rest = Math.max(rest + arrivals[i] - numPerDay, 0);

あとは、最終的に残った積み残し分が何日で処理可能かを計算して足してやればOK。 ただしここで、restもnumPerDayもともにint型であるため、小数点以下が切り捨てられてしまう。よって、そのままでは切り上げ処理ができない。 一度restまたはnumPerDayをdouble型にキャストする必要があることに注意。

operatedDays += Math.ceil((double)rest / numPerDay);

Problem Statement

When a widget breaks, it is sent to the widget repair shop, which is capable of repairing at most numPerDay widgets per day. Given a record of the number of widgets that arrive at the shop each morning, your task is to determine how many days the shop must operate to repair all the widgets, not counting any days the shop spends entirely idle.

For example, suppose the shop is capable of repairing at most 8 widgets per day, and over a stretch of 5 days, it receives 10, 0, 0, 4, and 20 widgets, respectively. The shop would operate on days 1 and 2, sit idle on day 3, and operate again on days 4 through 7. In total, the shop would operate for 6 days to repair all the widgets.

Create a class WidgetRepairs containing a method days that takes a sequence of arrival counts arrivals (of type int) and an int numPerDay, and calculates the number of days of operation.

Definition

  • Class: WidgetRepairs
  • Method: days
  • Parameters: int, int
  • Returns: int
  • Method signature: int days(int[] arrivals, int numPerDay) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Constraints

  • arrivals contains between 1 and 20 elements, inclusive.
  • Each element of arrivals is between 0 and 100, inclusive.
  • numPerDay is between 1 and 50, inclusive.

Solution

public class WidgetRepairs {

    public int days(int[] arrivals, int numPerDay) {
        int rest = 0;
        int operatedDays = 0;
        for (int i = 0; i < arrivals.length; i++) {
            if (rest == 0 && arrivals[i] == 0) continue;
            rest = Math.max(rest + arrivals[i] - numPerDay, 0);
            operatedDays++;

        }
        operatedDays += Math.ceil((double)rest / numPerDay);
        return operatedDays;
    }

}