ACM基地招新大会

NC217242. ACM基地招新大会

描述

万众瞩目的acm基地招新大会开始了。

基地的招新面试是排队进行的，但由于每个人都希望能早点加入基地，于是他们会插队。acmer之间的插队，当然会用编程能力说话。当某个人进行插队时，若在ta前面一位的同学编程能力不强于ta，ta会用能力(暴力)劝导(强迫)对方同意ta插队。若前面的同学能力强于ta，则ta可以送上一张大佬的签名进行贿赂而插队，但每个人只能有一张签名，所以这样的贿赂只能实现一次。

现在问你，对于每个人来说，在不考虑其他人插队的情况下，就仅有ta自己插队能够最终排到什么位置。

输入描述

第一行包括一个整数，代表参加基地招新面试的人数
第二行包括个整数，第个代表第一个人的能力值

输出描述

输出包括行，每行一个整数，第行的数代表原队列的第个人最终能排在第个位置，下标从1开始

示例1

输入:

7
3 1 4 5 6 2 8

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 302ms, 内存消耗: 6824K, 提交时间: 2021-01-16 23:06:20

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
stack<int>s;
int a[maxn];
int ans[maxn];
map<int,int>l;
int main(){
	a[0]=inf;
	s.push(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		while(a[s.top()]<=a[i])s.pop();
		l[i]=s.top();
		if(l[i]==0){
			cout<<1<<endl;
			ans[i]=1;
		}
		else{
			int k;
			if(a[i]>=a[i-1]&&l[i]==l[i-1])k=ans[i-1]-1;
			else k=l[i]-1;
			while(a[k]<=a[i])k--;
			cout<<k+1<<endl;
			ans[i]=k+1;
		}
		s.push(i);
	} 
}

上一题

下一题

详情