[开发测试]PAT (Advanced Level) Practice 1048 Find Coins (25 分) 凌宸1642

PAT (Advanced Level) Practice 1048 Find Coins (25 分) 凌宸1642

题目描述：

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 10⁵ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

译：Eva 喜欢从宇宙各处收集硬币，包括其他一些行星，如火星。 一天，她参观了一家可以接受各种硬币支付的万能购物中心。 但是，付款有一个特殊要求：每张账单，她只能用恰好两个硬币来支付确切的金额。 因为她身上有多达10⁵个硬币，她肯定需要你的帮助。 你应该告诉她，对于任何给定的金额，她是否能找到两枚硬币来支付。

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (≤10⁵, the total number of coins) and M (≤10³, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行包含 2 个正数：N（≤10⁵，硬币总数）和 M（≤10³，Eva 必须支付的金额）。 第二行包含N个面值的硬币，均为不超过500的正数。一行中的所有数字之间用空格隔开

output Specification (输出说明):

For each test case, print in one line the two face values V₁ and V₂ (separated by a space) such that V₁+V₂=M and V₁≤V₂. If such a solution is not unique, output the one with the smallest V₁. If there is no solution, output No Solution instead.

译：对于每个测试用例，在一行中打印两个面值 V1 和 V2(以空格分隔),使得 V₁+V₂=M 且 V₁≤V₂ 。 如果这样的解不唯一，则输出 V₁ 最小的解。 如果没有解决方案，则输出 No Solution 代替。

Sample Input1 (样例输入1):

8 15
1 2 8 7 2 4 11 15

Sample Output1 (样例输出1):

4 11

Sample Input2 (样例输入2):

7 14
1 8 7 2 4 11 15

Sample Output2 (样例输出2):

No Solution

The Idea：

• 经典的、简单的双指针问题。
• 将所有的数字按照升序排序，然后一头一尾指针，指向头尾两个元素，计算两个元素的和：
  • 如果元素的和刚好等于目标值，则直接输出 ，并返回；
  • 如果元素的和小于目标值，则左指针往右移 ；
  • 如果元素的和大于目标值。则右指针往左移 ；
  • 最后如果左指针的位置在右指针右边，则没有找到满足要求的解。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
int n , m ;
int main(){
	cin >> n >> m ;
	vector<int > num(n) ;
	for(int i = 0 ; i < n ; i ++) cin >> num[i] ;
	sort(num.begin() , num.end()) ; // 将输入的元素 升序排列
	int l = 0 , r = n - 1;
	while(l < r){
		if(num[l] + num[r] == m){
			cout << num[l] << ' ' << num[r] << endl ;	
			return 0 ;	
		}else if(num[l] + num[r] < m) l ++ ;
		else r -- ; 
	}
	cout << "No Solution" << endl ;
	return 0 ;
}