题目描述
伊娃喜欢从整个宇宙中收集硬币。
有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。
但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。
给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。
输入格式
第一行包含两个整数 N 和 M,分别表示硬币数量以及需要支付的金额。
第二行包含 N 个整数,表示每个硬币的面额。
输出格式
输出一行,包含两个整数 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
$O(n)$
对于m=x+y则y=m-x;
所以开标记数组 ,遍历原数组x ,看y是否存在就行
时间复杂度
$O(n)$
参考文献
C++ 代码
#include<bits/stdc++.h>
#define tcase int Case;cin>>Case;while(Case--)
#define closeiostream ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define bug2(a,b) cout<<a<<" "<<b<<endl
#define bug1(a) cout<<a<<endl
#define ll long long
#define N 100005
#define P pair<int,int>
#define fi first
#define se second
#define makep make_pair
#define ull unsigned long long
int nxt[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
ll qpow(ll a,ll b,ll mod) {
a%=mod;
ll res=1;
while(b) {
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
const ll mod=1e9+7;
using namespace std;
int a[N];
int b[N];
int main()
{
closeiostream;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
b[a[i]]++;
}
int ans=INT_MAX;
for(int i=1;i<=n;i++) {
int t=m-a[i];
if(t>0 && b[t] && t!=a[i]) {
ans=min(ans,t);
}
}
if(ans==INT_MAX) cout<<"No Solution"<<endl;
else bug2(ans,m-ans);
return 0;
}