第一道题要计算的是最小漂流船,已知每艘船最多可以承载2人,但是重量不能超过limit,求最少需要多少船只?
import java.util.Arrays; import java.util.Scanner; public class B4 { public int N = 2; public static void main(String[] args) { Scanner sc=new Scanner(System.in); String[] weightstr = sc.nextLine().split(" "); int limit = sc.nextInt(); int num = weightstr.length; int[] weight = new int[num]; for (int i = 0; i < weight.length; i++) { weight[i] = Integer.valueOf(weightstr[i]); } int result = getShipNum(weight, num, limit); System.out.println(result); } public static int getShipNum(int[] weight,int num, int limit){ int number = 0; Arrays.sort(weight); int i,j; for (i=num-1, j=0; i>=0 && j<=num-1 && j<i; i--) { number++; if(weight[i]+weight[j]<=limit){ j++; } } if(j==i){ number++; } return number; } }
第二道要计算主城之间的最小距离,应该是要用迪杰斯塔拉算法。时间不太够,没写出来。有大神AC出来的吗?
public class B5 { public static int N = 6; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int[][] relation = new int[N][N]; for (int i = 0; i < N; i++) { String[] vi = sc.nextLine().split(" "); for (int j = 0; j < N; j++) { relation[i][j] = Integer.valueOf(vi[j]); if(relation[i][j]==-1){ relation[i][j] = Integer.MAX_VALUE; } } } int[] shortestTime = getShortestTime(relation); for (int i = 1; i < N; i++) { System.out.println(shortestTime[i]); } } public static int[] getShortestTime(int[][] relation){ int[] shortestTime = new int[N]; shortestTime[0] = 0; int visited[] = new int[N]; visited[0] = 1; for (int i = 1; i < N; i++) { shortestTime[i] = relation[0][i]; } for (int times = 0; times < N; times++) { int position = 0; int min = Integer.MAX_VALUE; for (int i = 1; i < N; i++) { if(visited[i]==0){ if(min>shortestTime[i]){ min = Math.min(min, shortestTime[i]); position = i; } } } shortestTime[position] = min; visited[position]=1; for (int j = 1; j < N; j++) { int newdistance = shortestTime[position]+relation[position][j]; if(visited[j]==0 && relation[position][j]<Integer.MAX_VALUE && newdistance<shortestTime[j]){ shortestTime[j] = newdistance; } } } return shortestTime; } }
原文:https://www.cnblogs.com/haimishasha/p/11402513.html