C/C++数据结构——最优屏障（栈）

题目描述

M国的地势高低不平，现给出一个数组代表此国家某纬度上均匀分布的N座山的海拔高度H[i](任意两座山高度不同)，已知每座山的山顶上都有一座哨塔，若两个哨兵分别位于第i、j(i

输入描述:

第一行包含一个正整数T(T≤20)。
对于每组数据，第一行包含一个正整数n(2≤n≤50000)。
接下来n个不同的正整数，H1,H2,H3,…,Hn(0≤Hi≤109)分别代表横截面上每座山的海拔高度。
(读入数据比较大，建议使用scanf而不要使用cin读入)
对于60%的数据，n≤500
对于80%的数据，n≤5000
对于100%的数据，n≤50000

输出描述:

每组数据输出一行形如“Case #N: X C”,N代表当前是第N组数据（从1开始），X代表屏障放置在第X座山前可使M国的防守能力下降最多， 此时减少量为C。若有多种方案使得减少量为C，那么输出最小的X对应的方案。

示例1

输入

2
3
2 1 3
5
4 5 2 6 3

输出

Case #1: 2 2
Case #2: 3 2

链接：https://ac.nowcoder.com/acm/problem/14666
来源：牛客网

解题代码

#include
#include
#define MAX_SIZE 50005
struct STACK{
    int top;
    int num[MAX_SIZE];
}st;
void push(int data)
{
    st.num[++st.top]=data;
}
int isFull()
{
    if(st.top==54){
        return 1;
    }
    return 0;
}
int isEmpty()
{
    if(st.top==-1){
        return 1;
    }
    return 0;
}
int top()
{
    return st.num[st.top];
}
void pop()
{
    st.top--;
}
void clear()
{
    st.top=-1;
}
int main()
{
    st.top=-1;
    int T,n;
    int x,c,maxc;
    int num[50005];
    int ans[50005];
    int ans2[50005];
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        scanf("%d",&n);
        x=0;
        maxc=0;
        c=0;
        memset(ans,0,sizeof(ans));
        memset(ans2,0,sizeof(ans2));
        clear();
        for(int j=0;j<n;j++){
            scanf("%d",&num[j]);
            c=0;
            while(!isEmpty()&&top()<num[j]){
                c++;
                pop();
            }
            if(!isEmpty()){
                ans[j+1]=ans[j]+c+1;
            }else{
                ans[j+1]=ans[j]+c;
            }
            push(num[j]);
        }
        clear();
        for(int j=n-1;j>=0;j--){
            c=0;
            while(!isEmpty()&&top()<num[j]){
                c++;
                pop();
            }
            if(!isEmpty()){
                ans2[j+1]=ans2[j+2]+c+1;
            }else{
                ans2[j+1]=ans2[j+2]+c;
            }
            push(num[j]);
        }
        for(int j=1;j<=n-1;j++){
            if(maxc<ans[n]-ans[j]-ans2[j+1]){
                maxc=ans[n]-ans[j]-ans2[j+1];
                x=j;
            }
        }
        printf("Case #%d: %d %d\n",i,x+1,maxc);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

解题思路

最优屏障，他是说两个山峰能够监视到他们中间比他们矮的山峰，我们只需要把山峰序列从前到后和从后到前，利用栈，栈顶比当前山峰矮，那么出栈，且变量标识++，表示当前这座山峰能够监视到的山的数量，然后将他存储到数组中。判断当前山峰能够监视到的最大值就行，找到并记录，最后输出。大概这么个思路，没时间画图详解，有空了再详细解释吧。