题目描述
伊娃喜欢从整个宇宙中收集硬币。
有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。
但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。
给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。
输入格式
第一行包含两个整数 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),查找O(m),总时间复杂度O(n);
思路:数据范围是1000,可以直接用数组存储每一个值得数量,然后从1枚举到m/2
若i和m-i同时存在则为答案,若直至循环结束则无解
C++ 代码
#include"iostream"
#include"algorithm"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1010;
int q[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
q[a]+=1;
}
for(int i=1;i<=m/2;i++)
{
if(q[i]>=1)
{
q[i]-=1;
if(q[m-i]>=1)
{
cout<<i<<' '<<m-i;
return 0;
}
q[i]+=1;
}
}
cout<<"No Solution";
return 0;
}