[PAT解题报告] Find Coins
经典2-sum，问题，从一串数里找到两个和为m。做法： 把数组排序，然后用两头扫的办法。
i = 0, j = n - 1
如果a[i] + a[j] < m ,则需要放大, ++i
如果a[i] + a[j] > m, 则需要减小, --j
如果有解，第一次找到的一定是a[i]尽可能小的，这正是题目要求的。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int a[100005];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
sort(a, a + n);
bool mark = false;
for (int i = 0, j = n - 1; i < j; ) {
if (a[i] + a[j] == m) {
printf("%d %d\n",a[i],a[j]);
mark = true;
break;
}
if (a[i] + a[j] < m) {
++i;
}
else {
--j;
}
}
if (!mark) {
puts("No Solution");
}
return 0;
}
原题链接：http://www.patest.cn/contests/pat-a-practise/1048
查看10道真题和解析