盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 4957 Poor Mitsui(贪心, 大数, 想法)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4957

题意

有一个水龙头,单位时间出水为V。有n个破的水桶,每个水桶漏水的速度为ai,每个水桶要接到bi的水。现在问能否在某一时刻使得各个水桶符合条件,求最小的该时刻。
其中1≤n,v,ai,bi≤40

思路

考虑两个水桶,第一个为ai,bi,第二个为aj,bj。
把第一个排在前面的时间为: $\frac{b_j}{v-a_j}+\frac{\frac{a_i*b_j}{v-a_j}+b_i}{v-a_i}$

把第二个排在前面的时间为: $\frac{b_i}{v-a_i}+\frac{\frac{a_j*b_i}{v-a_i}+b_j}{v-a_j}$

所以可以发现只需要比较 ${b_i}\times{a_j}$ 和 ${b_j}\times{a_i}$

的大小即可

这道题有几个坑点:

  1. 如果水桶需要的水量不为零,且水桶漏水的速度大于v不行
  2. 如果水桶需要的水量为0时,所需要的时间应该是为0.
  3. 这道题的最后的答案可能非常大,超double了。我用了java中的BigDecimal
1
2
3
4
BigDecimal除一个数得到无限循环小数时会有问题,用:
BigDecimal.divide(BigDecimal, k, BigDecimal.ROUND_HALF_UP); 来保留k为小数
BigDecimal四舍五入:
BigDecimal.setScale(0, BigDecimal.ROUND_HALF_UP);

代码

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
import java.util.*;
import java.math.*;
public class Main {
static final int N = 50;
public static void main(String args[]) {
int[] a = new int[N];
int[] b = new int[N];
Scanner in = new Scanner(System.in);
int test_count = in.nextInt();
int n, v;
while (test_count -- > 0) {
n = in.nextInt();
v = in.nextInt();
int flag = 1;
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = in.nextInt();
if (a[i] >= v && b[i] != 0) flag = 0;
}
if (flag == 0) {
System.out.println(-1);
continue;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (b[i] * a[j] >= b[j] * a[i]) {
int tmp;
tmp = a[i]; a[i] = a[j]; a[j] = tmp;
tmp = b[i]; b[i] = b[j]; b[j] = tmp;
//swap(a[i], a[j]);
//swap(b[i], b[j]);
}
}
}
BigDecimal tot = BigDecimal.ZERO;
BigDecimal now;
for (int i = 0; i < n; i++) {
if (b[i] == 0) continue;
now = tot.multiply(BigDecimal.valueOf(a[i])).add(BigDecimal.valueOf(b[i]));
now = now.divide(BigDecimal.valueOf(v - a[i]), 200, BigDecimal.ROUND_HALF_UP);
tot = tot.add(now);
}
tot = tot.setScale(0, BigDecimal.ROUND_HALF_UP);
System.out.println(tot);
}
}
}

更新日志

  • 14209027 2015-07-27 23:02:04 Accepted 4957 436MS 13616K 1672 B Java SIO__Five