两个代码,玄学。
倒数第二个点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;
}
冷知识:第一个代码最后一个点 137ms,第二个代码倒数第二个点 41ms。