免费crm平台/重庆seo网站建设

重拾程序设计算法

暑假到了，准备将程序设计算法捡起来。虽达不到坊间大佬们的高水平，但也不想让自己的手太生。先从最简单的二分查找和快速排序开始。

题目描述

输入输出样例

AC Code

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll k[maxn] = {0},t[maxn] = {0};
inline bool cmp(const ll &n1,const ll &n2){return n1<n2;
}
ll n,m;
bool solve(int x){int l = 1,r = m,mid;while(l < r){mid = (l+r) >> 1;if(t[mid] == x)	return true;else if(t[mid] < x)	l = mid + 1;else				r = mid;}if(t[l] == x)	return true;return false;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>k[i];}for(int i=1;i<=m;i++){cin>>t[i];}sort(t+1,t+1+m,cmp);for(int i=1;i<=n;i++){if(solve(k[i])){cout<<k[i]<<' ';}}return 0;
}

解释

①明显是二分查找和快速排序的裸题。思路是：对特殊贡献奖数组的数进行自小到大的排序，对科技创新奖数组的数从下标1开始一直遍历到下标n，对每个数在特殊贡献奖数组中进行二分查找，看一下是否出现在特殊贡献奖数组中。
②查找：使用sort搭配cmp函数，此处不再赘述。
③二分查找：
在AcWing上偷学了一波。while循环的条件一定是 l<r，而mid使用mid = l+r >> 1，右移一位真的会快。而改变查找范围一定是l = mid + 1;r = mid;（当然用其他的方式也可以）。当l == r时，l即为查找的结果。