[UVA][模擬] 12608 - Garbage Collection
Problem G: Garbage Collection
Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either
- is full or
- cannnot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
- there are no more pick up points left
Given the weight limit that truck can carry and the list of pick up points with garbage weights, what is the distance that the truck will cover following the rules above?
Input Format
Input starts with an integer T on the first line, the number of test cases.
Each case starts with the line with two integers W and N, the weight limit and the number of pick up points, respectively.
Then N lines follow, each containing integers x_i and w_i, the distance
from the dump and the weight of the garbage at the pick up point
respectively.
Constraints are as given: 1<=W<=1000, 1<=N<=1000,
0<x_i<=100,000, 1<=w_i<=W. Distances are distinct and given
in order, i.e. for each i<j, x_i<x_j.
Output Format
For each test case output an integer on a line - the distance covered by the garbage truck.
Sample Input
3 2 2 1 1 2 2 6 3 1 1 2 2 3 3 3 3 1 2 2 2 3 1
Sample Output
8 6 10
Darko Aleksic
ACPC 2012
題目描述：
模擬垃圾車走的規則，計算走的總距離。
策略，滿的時候回去原點 0, 裝不下的時候回去原點 0, 所有點都被裝了回去原點 0
#include <stdio.h>
int main() {
int testcase, w, n;
int x[1005], ww[1005];
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &w, &n);
for(i = 0; i < n; i++)
scanf("%d %d", &x[i], &ww[i]);
int v = 0, ret = 0;
for(i = 0; i < n; i++) {
if(v + ww[i] == w) {
ret += x[i] + x[i];
v = 0;
} else if(v + ww[i] > w) {
ret += x[i] + x[i];
v = ww[i];
} else {
v += ww[i];
}
}
if(v) ret += x[n-1] + x[n-1];
printf("%d\n", ret);
}
return 0;
}