AcWing 1532. 找硬币
原题链接
简单
作者:
可持久化WA自动机
,
2021-01-19 00:18:41
,
所有人可见
,
阅读 431
算法1
$O(n)$
C++ 代码
#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
int mod = 1e9 +7;
int n,m,k;
//数据只有1e5直接用数组存即可
bool mp[maxn];
void solve(){
cin >> n >> m;
int ans = INF;
for(int i = 0 ; i < n ; ++i ){
int x;
cin >> x;
if(x >= m)continue;
//存在能匹配的另一枚硬币则更新答案
if(mp[m - x]){
ans = min(ans,min(x,m - x));
}
mp[x] = true;
}
if(ans == INF) cout << "No Solution" << endl;
else cout << ans << ' ' << m - ans << endl;
}
signed main(){
solve();
return 0;
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/