B. Preparing for Merge Sort

\(考虑的时候，千万不能按照题目意思一组一组去模拟\)

\(要发现每组的最后一个数一定大于下一组的最后一个数\)

\(那我们可以把a中的数一个一个填充到vec中\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+9;

vector<int>vec[maxn];

int a[maxn],cnt=1,n;

int find(int x)

{

	int l=1,r=cnt+1,mid,flag=0;//实际上取不到cnt+1,边界问题

	while(r>l)

	{

		mid=(l+r)/2;

		int len=vec[mid].size();

		if(len!=0&&vec[mid][len-1]<x)	flag=1,r=mid;

		else	l=mid+1;

	}

	if(flag==0)	return -1;

	else	return r;

}

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)	cin>>a[i];

	vec[1].push_back(a[1]);

	for(int i=2;i<=n;i++)

	{

		int res=find(a[i]);

		if(res==-1)	vec[++cnt].push_back(a[i]);

		else	vec[res].push_back(a[i]);

	}

	for(int i=1;i<=cnt;i++)

	{

		for(int j=0;j<vec[i].size();j++)

			cout<<vec[i][j]<<" ";

		cout<<endl;

	}

}

巴特西

B. Preparing for Merge Sort

最新文章

热门文章