A1048 Find Coins (25分).cpp

2020-02-04  本文已影响0人  km15

// 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;

}

上一篇 下一篇

猜你喜欢

热点阅读