扩展题
AcWing 2816.判断子序列
AcWing 1236.递增三元组
题目描述
对所有硬币的面额,确定对于给定的金额是否可以找到两个硬币来支付。
输出包含两个整数 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
算法1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>//哈希表:增删改查都是o(n);
using namespace std;
const int INF=10000;
int n,m;
int main(){
scanf("%d%d",&n,&m);
unordered_set<int >hash;
int v1=INF,v2;
for(int i=0;i<n;i++){
int a,b;
scanf("%d",&a);
b=m-a;
if(hash.count(m-a)){//查询哈希表中是否有b
hash.insert(a);//将a插入哈希表
if(a>b)swap(a,b);
if(a<v1){
v1=a,v2=b;
}
}
else{
hash.insert(a);//插入哈希表
}
}
if(v1==INF)printf("No Solution");
else printf("%d %d",v1,v2);
return 0;
}