// A1048 Find Coins (25分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
解题:
1、令int型a[]存放所有读入的数,并在读入数后进行排序,
2、枚举a[0]、a[1]...a[n - 1],对每个a[i],都用一次二分法查找是否有m - a[i]、
如果存在且下标不是i,则输出a[i]跟m - a[i],如果枚举完没发现,则输出no solution
learn && wrong:
1、二分法常常与for连用
2、使用二分查找发找到的是m - a[i],必须判读是否a[i],即下标相同,如果相同,则说明找到同一个位置的数字,应该跳过这种这种情况(这不应该作为特例吗,直接就跳过了?)
*/
include <iostream>
include <algorithm>
using namespace std;
int a[100010];
int bin(int left, int right, int key) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (a[mid] == key) return mid;
else if (a[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
int main()
{
int num, pay;
cin >> num >> pay;
for (int i = 0;i < num;++i) {
cin >> a[i];
}
sort(a, a + num);
int i;
for (i = 0;i < num;++i) {
int pos = bin(0, num - 1, pay - a[i]); //寻找pay - a[i]
if (pos != -1 && pos != i) {
cout << a[i] << " " << a[pos] << endl;
break;
}
}
if (i == num) cout << "No Solution\n";
return 0;
}
网友评论