これをどのようにo(n)またはoo(n^2)の代わりにo(log n)またはo(n)の時間複雑度を持つようにこのコードを修正する方法
授業が終わった後、児童のグループが外に出て、彼の誕生日を祝うためにポリカルプスを訪れることにしました。 i番目のグループはsiの友達(1≤si≤4)で構成されており、一緒にPolycarpusに行きたいと思っています。彼らはタクシーでそこに着くことに決めました。各車は最大4人の乗客を運ぶことができます。各グループのすべてのメンバーが同じタクシーに乗る必要がある場合、子どもが必要とする最小限の車の台数(1台のタクシーは複数のグループを利用できます) あなたはすべてのグループを検討する必要があるので、私のアプローチであるが、Oで(N^2)
import java.util.*;
public class taxi {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int cars = 0;
int groups = sc.nextInt();
int[] a = new int[groups];
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
for (int i = a.length - 1; i > 0; i--) {
if (a[i] == 4) {
cars = cars + 1;
} else {
if (a[i] == 0) {
break;
} else {
int y = 4 - a[i];
for (int j = i - 1; j >= 0; j--) {
if (y - a[j] == 0) {
a[j] = 0;
break;
}
if (y - a[j] > 0) {
y = y - a[j];
a[j] = 0;
}
}
cars = cars + 1;
Arrays.sort(a);
}
}
}
if (a[0] != 0) {
cars++;
}
System.out.println(cars);
cars = 0;
}
}
}
[codereview.se]に適しています。 –