专栏文章

题解：AT_donuts_2015_3 行列のできるドーナツ屋

zzhangmuning1016
AT_donuts_2015_3题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip2s1gs
此快照首次捕获于
2025/12/03 05:13
3 个月前
此快照最后确认于
2025/12/03 05:13
3 个月前
查看原文

题意

有 NN 个人在排队，每个人都有身高，要求出第 ii 个人向前能看到多少个人（要满足依次越来越高）。

方法 11 思路

此题是 单调栈 模板题。用单调栈维护一个身高一次递减的序列，第 ii 个答案为当前栈的长度。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
stack <int> q;
int a[100001], n;
int main () {
	ios :: sync_with_stdio (0);
	cin.tie (0);
  cout.tie (0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cout << q.size () << endl;
		while (q.size () && q.top () < a[i]) q.pop ();
		q.push (a[i]);
	}
	return 0;
}

方法 22 思路

再讲一种思路，线段数。
  1. 构建
    • 线段树的每个节点表示一个区间，根节点表示整个区间 [0, N-1]。每个内部节点将区间分为左右两部分，分别由左右子节点表示，直到叶子节点表示单个元素。
    • 每个节点存储区间最大值。叶子节点存储元素值，内部节点的值由其子节点的值合并得到。
  2. 查询
    • 当查询某个区间 [l, r] 的信息时，从根节点开始查找。若节点的区间在查询区间内，则返回该节点值。
    • 若当前节点的区间部分包含查询区间，将查询分解为对左右子节点的查询。
  3. 更新
    • 更新某个元素的值时，得向上更新路径上所有节点的值，使节点维护的始终正确。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
struct Node {
	vector<int>g;
	int n;
	Node(const vector<int>&arr) {
		n=arr.size();
		g.resize(4*n);
		build(1,0,n-1,arr);
	}
	void build(int xx,int start,int end,const vector<int>&arr) {
		if(start==end) {
			g[xx]=arr[start];
			return;
		}
		int mid=(start+end)/2;
		build(2*xx,start,mid,arr);
		build(2*xx+1,mid+1,end,arr);
		g[xx]=max(g[2*xx],g[2*xx+1]);
	}
	int query(int l,int r) {
		return query(1,0,n-1,l,r);
	}
	int query(int xx,int start,int end,int l,int r) {
		if(r<start||l>end) {
			return 0;
		}
		if(l<=start&&end<=r) {
			return g[xx];
		}
		int mid=(start+end)/2;
		int ll=query(2*xx,start,mid,l,r);
		int rr=query(2*xx+1,mid+1,end,l,r);
		return max(ll,rr);
	}
};
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int>A(n);
	for(int i=0; i<n; i++) {
		cin>>A[i];
	}
	Node segTree(A);
	stack<int>st;
	vector<int>res(n,0);
	for(int i=0; i<n; i++) {
		while(!st.empty()) {
			int j=st.top();
			int maxx=segTree.query(j+1,i-1);
			if(maxx>A[j]) {
				st.pop();
			} else {
				break;
			}
		}
		res[i]=st.size();
		st.push(i);
	}
	for(int i=0; i<n; i++) {
		cout<<res[i]<<endl;
	}
	cout<<endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...