題目

這題是給你一個環(huán)，讓你計算兩點之間最短距離。

• 環(huán)的任意兩點就兩條路，只要算出環(huán)長和任意一條路的大小，另一條就出來了
• 時間復(fù)雜度O（N）
• 提前計算前綴長度和即可

---

題解 C++

全部測試點通過

#include<iostream> #include<string> using namespace std; int main() {int total;cin >> total;int node[100005];int nSum[100005];nSum[0] = 0;long long sum = 0;for (int i = 0; i < total; i++) {cin >> node[i];sum += node[i];nSum[i + 1] = nSum[i] + node[i];}// 后面所有行long long d;long long m;cin >> m;for (int j = 0; j < m; j++) {d = 0;int n1, n2;cin >> n1 >> n2;n1 -= 1;// 對應(yīng)下標(biāo)n2 -= 1;// 最短距離 dis與sum - distance比較if (n1 < n2) {d = nSum[n2] - nSum[n1];d = d < sum - d ? d : sum - d;}else {d = nSum[n1] - nSum[n2];d = d < sum - d ? d : sum - d;}cout << d << "\n";} }

---

題解 Java

同樣的算法，2/3通過，剩下一個超時。代碼沒存。

---

O(n^2)版本（超時）

C++

2/3通過

#include<iostream> #include<string> using namespace std; int main() {int total;cin >> total;int node[100005];long long sum = 0;for (int i = 0; i < total; i++) {cin >> node[i];sum += node[i];}// 后面所有行long long d;long long m;cin >> m;for (int j = 0; j < m; j++) {d = 0;int n1, n2;cin >> n1 >> n2;n1 -= 1;// 對應(yīng)下標(biāo)n2 -= 1;// 最短距離 dis與sum - distance比較if (n1 < n2) {for (int k = n1; k < n2; k++) {d += node[k];}d = d < sum - d ? d : sum - d;}else {for (int k = n2; k < n1; k++) {d += node[k];}d = d < sum - d ? d : sum - d;}cout << d << "\n";}//system("pause"); }

Java

2/3通過

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws IOException {// 讀第一行BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String str = br.readLine();String[] arr = str.split(" ");int total = Integer.parseInt(arr[0]);int[] node = new int[total];long sum = 0;for (int i = 0; i < total; i++) {node[i] = Integer.parseInt(arr[i + 1]);sum += node[i];}// 后面所有行long d;long m = Integer.parseInt(br.readLine());for (int j = 0; j < m; j++) {d = 0;String s = br.readLine();String[] arr1 = s.split(" ");int n1 = Integer.parseInt(arr1[0]);int n2 = Integer.parseInt(arr1[1]);n1 -= 1;// 對應(yīng)下標(biāo)n2 -= 1;// 最短距離 dis與sum - distance比較if (n1 < n2) {for (int k = n1; k < n2; k++) {d += node[k];}d = d < sum - d ? d : sum - d;} else {for (int k = n2; k < n1; k++) {d += node[k];}d = d < sum - d ? d : sum - d;}System.out.println(d);}} }

總結(jié)

以上是生活随笔為你收集整理的【PAT甲级 环最短距离】1046 Shortest Distance (20 分) Java、C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。