美团8.27笔试第四题 麻烦大佬看一下
public class Solution4 {
static List<LinkedList<Integer>> finalResult = new ArrayList<>();
static LinkedList<Integer> result = new LinkedList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] tmp = scanner.nextLine().split(" ");
int clothCount = Integer.parseInt(tmp[0]);
int totalPower = Integer.parseInt(tmp[1]);
int[] powerCost = new int[clothCount];
String[] tmp2 = scanner.nextLine().split(" ");
for (int i = 0; i < clothCount; i++) {
powerCost[i] = Integer.parseInt(tmp2[i]);
}
int minPowerCost = Integer.MAX_VALUE;
int maxPowerCost = Integer.MIN_VALUE;
for (int i = 0; i < clothCount; i++) {
if (powerCost[i] < minPowerCost) {
minPowerCost = powerCost[i];
}
if (powerCost[i] > maxPowerCost) {
maxPowerCost = powerCost[i];
}
}
int[] timeCost = new int[clothCount];
String[] tmp3 = scanner.nextLine().split(" ");
for (int i = 0; i < clothCount; i++) {
timeCost[i] = Integer.parseInt(tmp3[i]);
}
//不能启动第一个机器人
if (powerCost[0] > totalPower) {
System.out.println(-1);
return;
}
int res = 0;
//必须要启动第一个机器人
res += timeCost[0];
totalPower = totalPower - powerCost[0];
//只能启动第一个机器人
if (totalPower < minPowerCost) {
System.out.println(clothCount * res);
return;
}
result.add(0);
boolean[] isStart = new boolean[clothCount];
isStart[0] = true;
traverse(totalPower, timeCost, powerCost, result, minPowerCost, maxPowerCost, isStart);
int finalRes = Integer.MAX_VALUE;
//求解最小时间
System.out.println(finalResult);
for (LinkedList<Integer> list : finalResult) {
res = 0;
if (list.size() == 1) {
res += clothCount * timeCost[0];
} else {
for (int i = 0; i < list.size(); i++) {
if (i == list.size() - 1) {
res += (clothCount - list.get(i)) * timeCost[i];
} else {
res += (list.get(i + 1) - list.get(i)) * timeCost[i];
}
}
}
finalRes = Math.min(res, finalRes);
}
System.out.println(finalRes);
}
public static void traverse(int totalPower, int[] timeCost, int[] powerCost, LinkedList<Integer> result, int minPowerCost, int maxPowerCost, boolean[] isStart) {
if (totalPower < minPowerCost) {
finalResult.add(new LinkedList<>(result));
return;
}
for (int i = 1; i < timeCost.length; i++) {
if (isStart[i] == false && powerCost[i] <= totalPower) {
result.add(i);
isStart[i] = true;
traverse(totalPower - powerCost[i], timeCost, powerCost, result, minPowerCost, maxPowerCost, isStart);
result.removeLast();
isStart[i] = false;
}
}
finalResult.add(new LinkedList<>(result));
}
}
第四题最后结果处理那一块没来得及写,但是我看了结果的组合是对的,分别对应启动哪几个机器人,还没提交不知道对不对
#美团笔试java#
static List<LinkedList<Integer>> finalResult = new ArrayList<>();
static LinkedList<Integer> result = new LinkedList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] tmp = scanner.nextLine().split(" ");
int clothCount = Integer.parseInt(tmp[0]);
int totalPower = Integer.parseInt(tmp[1]);
int[] powerCost = new int[clothCount];
String[] tmp2 = scanner.nextLine().split(" ");
for (int i = 0; i < clothCount; i++) {
powerCost[i] = Integer.parseInt(tmp2[i]);
}
int minPowerCost = Integer.MAX_VALUE;
int maxPowerCost = Integer.MIN_VALUE;
for (int i = 0; i < clothCount; i++) {
if (powerCost[i] < minPowerCost) {
minPowerCost = powerCost[i];
}
if (powerCost[i] > maxPowerCost) {
maxPowerCost = powerCost[i];
}
}
int[] timeCost = new int[clothCount];
String[] tmp3 = scanner.nextLine().split(" ");
for (int i = 0; i < clothCount; i++) {
timeCost[i] = Integer.parseInt(tmp3[i]);
}
//不能启动第一个机器人
if (powerCost[0] > totalPower) {
System.out.println(-1);
return;
}
int res = 0;
//必须要启动第一个机器人
res += timeCost[0];
totalPower = totalPower - powerCost[0];
//只能启动第一个机器人
if (totalPower < minPowerCost) {
System.out.println(clothCount * res);
return;
}
result.add(0);
boolean[] isStart = new boolean[clothCount];
isStart[0] = true;
traverse(totalPower, timeCost, powerCost, result, minPowerCost, maxPowerCost, isStart);
int finalRes = Integer.MAX_VALUE;
//求解最小时间
System.out.println(finalResult);
for (LinkedList<Integer> list : finalResult) {
res = 0;
if (list.size() == 1) {
res += clothCount * timeCost[0];
} else {
for (int i = 0; i < list.size(); i++) {
if (i == list.size() - 1) {
res += (clothCount - list.get(i)) * timeCost[i];
} else {
res += (list.get(i + 1) - list.get(i)) * timeCost[i];
}
}
}
finalRes = Math.min(res, finalRes);
}
System.out.println(finalRes);
}
public static void traverse(int totalPower, int[] timeCost, int[] powerCost, LinkedList<Integer> result, int minPowerCost, int maxPowerCost, boolean[] isStart) {
if (totalPower < minPowerCost) {
finalResult.add(new LinkedList<>(result));
return;
}
for (int i = 1; i < timeCost.length; i++) {
if (isStart[i] == false && powerCost[i] <= totalPower) {
result.add(i);
isStart[i] = true;
traverse(totalPower - powerCost[i], timeCost, powerCost, result, minPowerCost, maxPowerCost, isStart);
result.removeLast();
isStart[i] = false;
}
}
finalResult.add(new LinkedList<>(result));
}
}
第四题最后结果处理那一块没来得及写,但是我看了结果的组合是对的,分别对应启动哪几个机器人,还没提交不知道对不对
#美团笔试java#