同志们,红温了,玄关
查看原帖
同志们,红温了,玄关
964645
pies_0x楼主2024/8/30 16:12

两个代码,玄学。

倒数第二个点T:

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

#define N 500005

int n,k;
int ans[N];
vector<priority_queue<int,vector<int>,greater<int> > > cards;

bool cmp(priority_queue<int,vector<int>,greater<int> > a,priority_queue<int,vector<int>,greater<int> > b){return a.top()<b.top();}

signed main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
	{
		int ins;
		scanf("%d",&ins);
		priority_queue<int,vector<int>,greater<int> > temp;
		temp.push(ins);
		vector<priority_queue<int,vector<int>,greater<int> > >::iterator jt=upper_bound(cards.begin(),cards.end(),temp,cmp);
		if(jt!=cards.end())
		{
			jt->push(ins);
			if(jt->size()==(unsigned long long)(k))
			{
				while(jt->size())
				{
					int temp=jt->top();jt->pop();
					ans[temp]=i;
				}
				cards.erase(jt);
			}
		}
		else
		{
			if(temp.size()==(unsigned long long)(k))
				while(temp.size())
				{
					int t=temp.top();temp.pop();
					ans[t]=i;
				}
			else cards.push_back(temp);
		}
	}
	for(int i=1;i<=n;++i)
		printf("%d\n",ans[i]==0?-1:ans[i]);
	return 0;
}

最后一个点T:

// LUOGU_RID: 175367876
#include<cstdio>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

#define N 200005

int n,k;
int ans[N];
vector<priority_queue<int,vector<int>,greater<int> > > cards;

signed main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
	{
		int ins;
		scanf("%d",&ins);
		bool flag=1;
		for(auto jt=cards.begin();jt!=cards.end();++jt)
		{
			auto &j=*jt;
			if(j.top()>ins)
			{
				flag=0;
				j.push(ins);
				if(j.size()==(unsigned long long)(k))
				{
					while(j.size())
					{
						int temp=j.top();j.pop();
						ans[temp]=i;
					}
					cards.erase(jt);
				}
				break;
			}
		}
		if(flag)
		{
			priority_queue<int,vector<int>,greater<int> > temp;
			temp.push(ins);
			if(temp.size()==(unsigned long long)(k))
				while(temp.size())
				{
					int t=temp.top();temp.pop();
					ans[t]=i;
				}
			else cards.push_back(temp);
		}
	}
	for(auto i:cards)
		while(i.size())
		{
			int temp=i.top();i.pop();
			ans[temp]=-1;
		}
	for(int i=1;i<=n;++i)
		printf("%d\n",ans[i]);
	return 0;
}

冷知识:第一个代码最后一个点 137ms137ms,第二个代码倒数第二个点 41ms41ms。

2024/8/30 16:12
加载中...