找硬币
题目来源：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 %dn", v1, v2);
} else {
System.out.println("No Solution");
}
}
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
