题目描述
对所有硬币的面额,确定对于给定的金额是否可以找到两个硬币来支付。
输出包含两个整数 V1,V2,表示所选的两个硬币的面额,使得 V1≤V2 并且 V1+V2=M。
如果答案不唯一,则输出 V1 最小的解。
如果无解,则输出 No Solution。
数据范围
1≤N≤105,
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
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
//双指针:数组要排序,要有单调性,i:1-->n,j:n-->1,i<j
// |————>前一个指针从前往后走,后一个指针一定从后往前走,就可以用双指针做法
//
const int N=100010;
int n,m;
int w[N];//存硬币的面额
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>w[i];
sort(w,w+n);
for(int i=0,j=n-1;i<j;i++){
while(i<j&&w[i]+w[j]>m)j--;//对每个i,枚举j是否可以
if(i<j&&w[i]+w[j]==m){
cout<<w[i]<<" "<<w[j];//找到的第一个就是答案
return 0;
}
}
cout<<"No Solution";
return 0;
}