洛谷U420301题解

题解

方法一枚举

时间复杂度$O(n^2)$
主要代码

int main()
{int n,t;cin >> n;for(int i = 1;i <= n;i++)   cin >> a[i];cin >> t;for(int i = 1;i <= n;i++){for(int j = i + 1;j <= n;j++){if(a[i] + a[j] == t){cout << "Yes" << endl;return 0;}}}cout << "No" << endl;return 0;
}

方法二二分查找

先选定 $a_i$，然后在数组 $a$ 里找找 $t-a_i$ 有没有
时间复杂度 $O(nlogn)$

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[1000010];
bool check(int x,int i)
{int* k = lower_bound(a + i + 1,a + n + 1,x);if(k - a > n)   return false;return *k == x;
}
signed main()
{cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}int t;cin >> t;for(int i = 1;i <= n;i++){int x = t - a[i];if(check(x,i)){cout << "Yes" << endl;return 0;}}cout << "No" << endl;return 0;
}