• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

牛客第二场k题stack

admin

11月 28, 2021

1.k题stack

题意:

给你一个数组,再给你一个栈,把数组里面的数放到栈里面,如果栈头大,就弹出,每次i,记录栈的大小。现在给你一些i对应栈的大小,求出一种符合的数组。

思路:

模拟单调栈的过程,从大到小赋值,对于要弹出的元素,一定是大的,那么让他从n开始赋值,对于在栈里面的元素,可以倒叙赋值。
利用栈st记录每次元素的下标,对于弹出的元素,直接赋值。完了以后再对栈里面的元素赋值。

代码:

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define INF 0x7f7f7f7f
#define endl '
'
#define mem(a, b) memset(a, b, sizeof(a))
#define open freopen("ii.txt", "r", stdin)
#define close freopen("oo.txt", "w", stdout)
#define IO                       
	ios::sync_with_stdio(false); 
	cin.tie(0);                  
	cout.tie(0)
#define pb push_back
using namespace std;
typedef pair<ll, ll> PII;
const int N = 2e6 + 10;
const double PI = 3.1415926535898;
const ll mod = 1e9 + 7;
ll a[N];
ll b[N];
stack<ll> st;
int main()
{
	ll n, k;
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		cin >> b[x];
	}
	ll x = n;
	for (int i = 1; i <= n; i++)
	{
		if (b[i])
		{
			if (b[i] > st.size()+1)
			{
				cout << -1 << endl;
				return 0;
			}
			while (b[i] <= st.size())
			{
				a[st.top()]=x--;
				st.pop();
			}
		}
		st.push(i);
	}
	while(!st.empty())
	{
		a[st.top()]=x--;
		st.pop();
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。