アルゴリズムゲーム:棒を切る
1153 ワード
m本の棒、n本の同じ長さの小さな棒(m
注意:棒はつなぎ合わせてはいけません.
注意:棒はつなぎ合わせてはいけません.
public class QieMuGun {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
double[] a = new double[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextDouble();
}
sc.close();
double value = solve(a, n);
DecimalFormat df = new DecimalFormat("#.00");
System.out.println(df.format(value));
}
public static double solve(double[] a, int n) {
sortBiger(a);
double r = a[0];
double l = 0.0;
double m = l / 2;
while (true) {
int sum = 0;
m = (l + r) / 2;
for (int i = 0; i < a.length; i++) {
sum += a[i] / m;
}
if (sum >= n) {
l = m;
} else {
r = m;
}
if (sum == n && (r - l) < 0.001) {
break;
}
}
return m;
}
public static void sortBiger(double[] a) {
int x;
double temp;
for (int i = 0; i < a.length - 1; i++) {
x = i;
for (int j = i + 1; j < a.length; j++) {
if (a[x] > a[j]) {
x = j;
}
}
if (x != i) {
temp = a[x];
a[x] = a[i];
a[i] = temp;
}
}
}
}