题目描述
打表
先将所有硬币面额排序并在d数组里面标记该枚硬币
后续遍历一边排好序的硬币数组即可
时间复杂度
O(n)
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int N, M,dp[100010];
bool d[1010];
cin >> N >> M;
memset(d, 0, sizeof d);
for (int i = 1; i <= N; i++)
{
int a;
cin >> a;
dp[i] = a;
d[a]=1;
}
sort(dp + 1, dp + 1 + N);
for (int i = N; i >=1; i--)
{
if (M <= dp[i])continue;
int k = M - dp[i];
d[dp[i]] = 0;
if (d[k])
{
cout << k << " " << dp[i];
return 0;
}
}
cout << "No Solution";
}