Apple Trees
Time Limit: 1 Sec Memory Limit: 128 MB
小Y在x轴上种了好多苹果树,第i棵苹果树在p[i]的位置上,树上有a[i]个苹果。
现在小Y在坐标原点,拿着一个容量为K的篮子。
由于小Y很懒,他想求出最少移动多少距离才能够把所有树上的苹果摘下来并且运送到坐标原点。

传送门:SHUOJ1951

Input

多组数据,第一行有一个整数T表示数据组数。(T <= 20) 之后有T组数据,每组数据第一行为两个整数N和K,表示苹果树的数量和篮子的容量。 (1 <= N <= 1000, 1 <= K <= 100000) 接着有N行,每行有两个整数 p[i] 和 a[i] 分别表示苹果树的坐标及苹果的数量。 (0 <= p[i] <= 1000, 1 <= a[i] <= 1000)

Output

对于每组数据,输出一行整数,表示小Y最少需要移动的距离。

Sample Input

1
2
3
4
5
1
3 2
1 3
2 1
3 2

Sample Output

1
12

题解

典型排序加贪心题,但我一开始想的是先去拿最多的...写了一半想出反例了...那只有先去拿最远了。 按从远到近排序,设一个变量保存手上拿的苹果。接下来就是模拟人拿苹果的过程了 一个变量temp存人目前有的苹果个数,还需要一个pre存当前的最远下标(因为当拿不满时往下一个走的时候其实是从远走到近了,因为一开始是从远到近排序的,所以需要存一下最远的那个下标) 然后就没什么坑了...
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.*; 
import java.util.*;
public class Main {
static class Tree implements Comparable<Tree>{
int pos;
int count;
@Override
public int compareTo(Tree o) {
if(this.pos>o.pos){ //按从远到近排序
return -1;
}
else
return 1;
}

}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int o=sc.nextInt();
for(int z=1;z<=o;z++){
int n=sc.nextInt();
int k=sc.nextInt();
Tree[]tree=new Tree[n]; //n个结点
int total=0;
for(int i=0;i<n;i++){
tree[i]=new Tree();
tree[i].pos=sc.nextInt();
tree[i].count=sc.nextInt();
total+=tree[i].count;
}
Arrays.sort(tree); //排序
/*for(Tree t:tree){
System.out.println(t.pos);
}*/
int temp=0;
int result=0;
int pre=0;
int flag=1;
for(int i=0;i<n;i++){ //从远到近排序
while(tree[i].count+temp>=k){ //如果手上的苹果能在这棵树上拿满
if(temp>0){ //如果手上拿着前面的苹果
tree[i].count=tree[i].count-(k-temp); //在这棵树上拿满
result+=2*pre; //加上距离
temp=0; //清空手上
flag=1;} //表示下一次没拿满时要记录下坐标
else{
tree[i].count=tree[i].count-(k-temp);
result+=2*tree[i].pos;
}
}
if(tree[i].count>0&&flag==1){ //如果那棵树没正好拿完,且是第一次没拿完,记录下标,即最远的距离
temp+=tree[i].count;
tree[i].count=0;
pre=tree[i].pos;
flag=0;
}
else if(tree[i].count>0){
temp+=tree[i].count;
tree[i].count=0;
}
}
if(temp>0){ //最后手上还有苹果的话,还得走一次
result+=2*pre;
}
System.out.println(result);
}
}
}