PAT 甲级 1048 Find Coins 二分的写法

本文主要是介绍PAT 甲级 1048 Find Coins 二分的写法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PAT 甲级 1048 Find Coins 二分的写法

散列的写法非常简单明了，LeetCode Problem List很前面就有类似的题。其实这道题用二分实现也是可以的，下面是二分的写法。之后准备做一个二分的专题总结。

#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint N, M;cin >> N >> M;vector<int> coins(N);for (auto& i : coins) cin >> i;sort(coins.begin(), coins.end());for (int i = 0; i < N; ++i) {int need_to_find = M - coins[i];// 二分, 找到第一个大于等于need_to_find的数// 对于重复元素，第一次走到这里的时候会退出，但是下面的判断beg==i过不了// 然后i+1，下一次判断的时候得到的beg仍然是第i位的，所以没有问题int beg = 0, end = N, mid;while (beg < end) {mid = beg + (end - beg) / 2;if (coins[mid] < need_to_find) {beg = mid + 1;}else {end = mid;}}if (coins[beg] == need_to_find && beg != i) {printf("%d %d\n", coins[i], coins[beg]);return 0;}}cout << "No Solution";return 0;
}

这篇关于PAT 甲级 1048 Find Coins 二分的写法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---