A30167.和为给定数

手搓算法才有意思

#include <iostream>
//#include <algorithm>
using namespace std;

int n, m;
int a[100005], t[100005];

//归并排序(可以使用其他O(nlogn)排序代替)
void merge_sort(int a[], int left, int right) {
    if (left >= right) return;
    int mid = left+right>>1;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);
    int i=left, j=mid+1, k=0;
    while (i<=mid && j<=right) {
        if (a[i] <= a[j]) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= right) t[k++] = a[j++];
    for (int i=0; i<k; i++) {
        a[left+i] = t[i];
    }
}

//二分查找(可以使用binary_search()代替)
bool binsearch(int a[], int left, int right, int target) {
	if (left > right) return false;//查找结束，没找到
	int mid = left+right>>1;
    //缩减问题规模
	if (a[mid] > target) return binsearch(a, left, mid-1, target);
	else if (a[mid] < target) return binsearch(a, mid+1, right, target);
	return true;//找到了
}

int main() {
    //加快输入输出(不总要)
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    //输入数据(不重要)
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    cin >> m;
    //排序(二分查找要有序, 不重要)
    merge_sort(a, 1, n);
    for (int i=1; i<=n; i++) {
        //一点点小优化(不加也行, 不重要)
    	if (a[i]==a[i-1] && i>1) continue;
        //m-a[i]是查找的目标值, 也是唯一能和a[i]配对的数
    	if (binsearch(a, 1, n, m-a[i])) {
            //如果能找到就输出数据, 结束程序
    		cout << a[i] << ' ' << m-a[i];
    		return 0;//不结束程序会输出所有可能数对
		}
	}
    //找不到就输出"No"
	cout << "No";
    return 0;
}