6675.你学完了？我羡慕了

本题设置的数据量在1e5的范围，要利用快排（quick_sort）和二分查找，不然会直接超时（当然，佬可以用map过）

注意加粗部分：“按在学科A中学号名单的先后次序输出”

这提醒我们学科A的学号名单是不能排序的，必须保留原有的次序状态。

那我们就只能对学科B进行排序，由于数据量比较大，防止超时就必须用快排算法。

void q_sort(int low,int high)//快排
{
	if(low>high)return;
	int temp = g[low];
	int l=low,r=high;
	while(l!=r)
	{
		while(g[r]>=temp&&l<r)r--;
		while(g[l]<=temp&&l<r)l++;
		if(l<r)swap(g[l],g[r]);
	}
	g[low]=g[l];
	g[l]=temp;
	q_sort(low,l-1);
	q_sort(l+1,high);
}

再循环遍历学科A中的学号名单，分别查找是否在学科B中的名单中出现，老样子，数据量比较大，查询也得用二分查找。

int find(int x)//二分查找
{
	int l=0,r=m-1;
	while(l <= r)
	{
		int mid = (l+r+1)/2;
		if(g[mid]>=x)r=mid-1;
		else l=mid+1;
	}
	if(g[l]==x&&l<m&&l>=0)return l;
	return -1;
}

只要能够在学科B名单中查到当前数字，即可直接保存到一个临时数组（因为这道题输出的末尾没有空格，所以不能直接输出）

完整代码：

#include <bits/stdc++.h>
using namespace std;
int k[100001],g[100001];
int n,m;
int find(int x)//二分查找
{
	int l=0,r=m-1;
	while(l <= r)
	{
		int mid = (l+r+1)/2;
		if(g[mid]>=x)r=mid-1;
		else l=mid+1;
	}
	if(g[l]==x&&l<m&&l>=0)return l;
	return -1;
}
void q_sort(int low,int high)//快排
{
	if(low>high)return;
	int temp = g[low];
	int l=low,r=high;
	while(l!=r)
	{
		while(g[r]>=temp&&l<r)r--;
		while(g[l]<=temp&&l<r)l++;
		if(l<r)swap(g[l],g[r]);
	}
	g[low]=g[l];
	g[l]=temp;
	q_sort(low,l-1);
	q_sort(l+1,high);
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)scanf("%d",&k[i]);
	for(int i=0;i<m;i++)scanf("%d",&g[i]);
	int j=0;
	int gcc[n];
	q_sort(0,m-1);
	for(int i=0;i<n;i++)
	{
		int temp = find(k[i]);
		if(temp!=-1)gcc[j++]=k[i];
	}
	for(int i=0;i<j;i++)
	{
		if(i!=j-1)cout<<gcc[i]<<" ";
		else cout<<gcc[i];
	}
	return 0;
}