|
|
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 vector <int>) and an int numPerDay, and calculates the number of days of operation. | Definition | | | | Class: | WidgetRepairs | | Method: | days | | Parameters: | vector <int>, int | | Returns: | int | | Method signature: | int days(vector <int> arrivals, int numPerDay) | | (be sure your method is public) | | | |
| 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. | Examples | | 0) |
| | | | | 1) |
| | | | | 2) |
| | | | | 3) |
| | | | | 4) |
| | | { 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6 } | 3 | | Returns: 15 |
| | This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. 直接遍歷就行，每天完成不了的留到第二天做。最后沒有完成的延遲到后面做。 求的的做的天數是多少，沒有做的那天不用算。 228PT，速度還是慢了點。 #include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
class WidgetRepairs{
public:
int days(vector <int> arrivals, int numPerDay){
int n=arrivals.size();
int now=0;
int i=0;
int tot=0;
while (i<n || now) //這里可以優化一下，如果i==n就不用循環了，剩下的需要完成的天數為(now-1)/numPerDay+1。
{
if (i<n)
now+=arrivals[i];
if (now>0) //第一次這里理解錯了，以后要把細節搞清楚啊。。。
tot++;
now=now>numPerDay?now-numPerDay:0;
i++;
}
return tot;
}
};
|