找硬幣
題目來源：PAT甲級真題1048
時間限制：1000ms 記憶體限制：64mb
題目描述
伊娃喜歡從整個宇宙中收集硬幣，
有一天，她去了一家宇宙購物中心購物，結賬時可以使用各種硬幣付款，
但是，有一個特殊的付款要求：每張帳單，她只能使用 恰好 兩個硬幣來 準確 的支付消費金額，
給定她擁有的所有硬幣的面額，請你幫她確定對于給定的金額，她是否可以找到兩個硬幣來支付，
輸入格式
第一行包含兩個整數 \(N\) 和 \(M\)，分別表示硬幣數量以及需要支付的金額，
第二行包含 \(N\) 個整數，表示每個硬幣的面額，
輸出格式
輸出一行，包含兩個整數 \(V_1\),\(V_2\)，表示所選的兩個硬幣的面額，使得 \(V_1 ≤ V_2\) 并且 \(V_1 + V_2 = M\)，
如果答案不唯一，則輸出 \(V_1\) 最小的解，
如果無解，則輸出 No Solution ，
資料范圍
\(1 ≤ N ≤ 10^5\),
\(1 ≤ M ≤ 1000\)
樣例輸入1
8 15
1 2 8 7 2 4 11 15
樣例輸出1
4 11
樣例輸入2
7 14
1 8 7 2 4 11 15
樣例輸出2
No Solution
解題思路:左右指標
需要首先對給定的硬幣陣列進行排序，
排序后將左指標指向陣列的首項，右指標指向尾項，
如果兩個指標所指的硬幣加起來大于了需要支付的金額，則將右指標向左移動一格，
如果兩個數加起來小于支付金額，則左指標向右移，
直到他們加起來與支付金額相等，則跳出回圈，
當回圈結束，沒有找到加起來與支付金額相等的結果，則輸出 No Solution ，
先對給定的硬幣陣列進行排序，然后定義兩個指標，分別指向最小和最大，
假設陣列為a，兩個指標分別為left、right，就有以下情況
\(
\begin{cases}
1.a[left] + a[right] > m , 兩者相加比金額大，說明右指標所指的值大了，需要將右指標左移一項， \\
2.a[left] + a[right] < m , 兩者相加比金額小，說明左指標的值小了，將左指標右移一項， \\
3.a[left] + a[right] == m , 兩者相加等于金額，則找到了所需值，
\end{cases}
\)
解題代碼-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
}
input.close();
Arrays.sort(a);
int v1 = -1, v2 = -1;
int left = 0, right = n - 1; //左右兩個指標
while (left < right) {
if (a[left] + a[right] == m) {
v1 = a[left];
v2 = a[right];
break;
} else if (a[left] + a[right] > m) {
right--;
} else {
left++;
}
}
if (v1 >= 1) {
System.out.printf("%d %d\n", v1, v2);
} else {
System.out.println("No Solution");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251487.html
標籤：其他