AcWing 1532. 找硬币
原题链接
简单
作者:
wjie
,
2021-01-19 10:48:37
,
所有人可见
,
阅读 226
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int arr[N];
bool binary_find(int l, int r, int target)
{
while (l <= r)
{
int mid = (l + r) >> 1;
if (arr[mid] == target) return true;
if (arr[mid] > target) r = mid - 1;
else l = mid + 1;
}
return false;
}
bool work(int n, int target)
{
for (int i = 0; i < n-1; ++i)
{
if (target - arr[i] < arr[i]) return false;
if (binary_find(i+1, n-1, target-arr[i]))
{
printf("%d %d", arr[i], target-arr[i]);
return true;
}
}
return false;
}
int main()
{
int n, target;
scanf("%d%d", &n, &target);
for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
sort(arr, arr+n);
if (!work(n, target)) puts("No Solution");
return 0;
}