单调栈

2020-03-07

数据结构与算法

字数统计: 519字 | 阅读时长≈ 2分钟

单调栈的总结

题目传送门：Gym-100971D Laying Cables

题目大意：

给定你一些城市（直线）的坐标和城市人口大小，要求你输出距离每个城市最近的比他人口大的城市标号，如果没有，则置为-1。

解题思路：

维护一个单调递减的栈，分别从左到右，在从右到左，分别计算离他最近的点。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
struct Node
{
    ll loc, v, num;
}node[maxn];
bool cmp(Node x, Node y)
{
    return x.loc < y.loc;
}
ll aim[maxn];
int main()
{
    ll n, m, i, j, k, a, b;
    scanf("%lld", &m);
    for(i = 1; i <= m; i++)
    {
        scanf("%lld %lld", &a, &b);
        node[i].loc = a;
        node[i].v = b;
        node[i].num = i;
    }
    sort(node + 1, node + 1 + m, cmp);
    stack<Node>s;
    vector<Node>lef, rig;
    lef.resize(maxn);
    rig.resize(maxn);
    Node w;
    w.v = w.loc = 2e10;
    w.num = -1;
    s.push(w);
    for(i = 1; i <= m; i++)
    {
        while(node[i].v > s.top().v)s.pop();
        lef[i] = s.top();
        s.push(node[i]);
    }
    while(!s.empty())s.pop();
    node[m + 1].v = 2e10;
    node[m + 1].loc = 2e10;
    node[m + 1].num = -1;
    s.push(node[m + 1]);
    for(i = m; i >= 1; i--)
    {
        while(node[i].v > s.top().v)s.pop();
        rig[i] = s.top();
        s.push(node[i]);
    }
    for(i = 1; i <= m; i++)
    {
        if(abs(lef[i].loc - node[i].loc) == abs(rig[i].loc - node[i].loc))
        {
            if(lef[i].v > rig[i].v)aim[node[i].num] = lef[i].num;
            else aim[node[i].num] = rig[i].num;
        }
        else if(abs(lef[i].loc - node[i].loc) > abs(rig[i].loc - node[i].loc))
        {
            aim[node[i].num] = rig[i].num;
        }
        else aim[node[i].num] = lef[i].num;
    }
    for(i = 1; i <= m; i++)
    {
        if(i != 1)printf(" ");
        printf("%lld", aim[i]);
    }
    printf("\n");
    return 0;
}

1	#include <bits/stdc++.h>
2	using namespace std;
3	typedef long long ll;
4	const int maxn = 200005;
5	struct Node
6	{
7	ll loc, v, num;
8	}node[maxn];
9	bool cmp(Node x, Node y)
10	{
11	return x.loc < y.loc;
12	}
13	ll aim[maxn];
14	int main()
15	{
16	ll n, m, i, j, k, a, b;
17	scanf("%lld", &m);
18	for(i = 1; i <= m; i++)
19	{
20	scanf("%lld %lld", &a, &b);
21	node[i].loc = a;
22	node[i].v = b;
23	node[i].num = i;
24	}
25	sort(node + 1, node + 1 + m, cmp);
26	stack<Node>s;
27	vector<Node>lef, rig;
28	lef.resize(maxn);
29	rig.resize(maxn);
30	Node w;
31	w.v = w.loc = 2e10;
32	w.num = -1;
33	s.push(w);
34	for(i = 1; i <= m; i++)
35	{
36	while(node[i].v > s.top().v)s.pop();
37	lef[i] = s.top();
38	s.push(node[i]);
39	}
40	while(!s.empty())s.pop();
41	node[m + 1].v = 2e10;
42	node[m + 1].loc = 2e10;
43	node[m + 1].num = -1;
44	s.push(node[m + 1]);
45	for(i = m; i >= 1; i--)
46	{
47	while(node[i].v > s.top().v)s.pop();
48	rig[i] = s.top();
49	s.push(node[i]);
50	}
51	for(i = 1; i <= m; i++)
52	{
53	if(abs(lef[i].loc - node[i].loc) == abs(rig[i].loc - node[i].loc))
54	{
55	if(lef[i].v > rig[i].v)aim[node[i].num] = lef[i].num;
56	else aim[node[i].num] = rig[i].num;
57	}
58	else if(abs(lef[i].loc - node[i].loc) > abs(rig[i].loc - node[i].loc))
59	{
60	aim[node[i].num] = rig[i].num;
61	}
62	else aim[node[i].num] = lef[i].num;
63	}
64	for(i = 1; i <= m; i++)
65	{
66	if(i != 1)printf(" ");
67	printf("%lld", aim[i]);
68	}
69	printf("\n");
70	return 0;
71	}