最优屏障

思路

插入屏障就是将一个区间分割成两个区间[1,x]和[x+1,n]，所以我们可以利用栈来求出前缀的对数和、后缀的对数和，然后在一个for循环来寻找最大值，减少的最大防守力就是[1,n] - [1,x] - [x+1,n],最优的屏障放置位置就是当前的x+1。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int maxn = 5e4 + 10; 

int n,t,x,ans,flag,num,a[maxn],v1[maxn],v2[maxn];
stack<int> s;

inline void init(){
    ans = 0,flag = 0;
    memset(v1,0,sizeof(v1));
    memset(v2,0,sizeof(v2));
}

int main(){
    cin>>t;
    for(int i = 1; i <= t; i++){
        scanf("%d",&n);

        init();

        for(int j = 1; j <= n; j++)
            scanf("%d",&a[j]);

        while(!s.empty())    s.pop();
        for(int j = 1; j <= n; j++){
            v1[j] = v1[j-1];
            num = 0;
            while(!s.empty() && s.top() < a[j]){
                num++;
                s.pop();
            }
            if(!s.empty())    v1[j] += num + 1;
            else    v1[j] += num;
            s.push(a[j]);
        }

        while(!s.empty())    s.pop();
        for(int j = n; j >= 1; j--){
            v2[j] = v2[j+1];
            num = 0;
            while(!s.empty() && s.top() < a[j]){
                num++;
                s.pop();
            }
            if(!s.empty())    v2[j] += num + 1;
            else    v2[j] += num;
            s.push(a[j]);
        }

        for(int j = 1; j <= n; j++){
            if(v1[n] - v1[j] - v2[j+1] > ans){
                ans = v1[n] - v1[j] - v2[j+1];
                flag = j + 1;
            }
        }
        printf("Case #%d: %d %d\n",i,flag,ans);
    } 
    return 0;
}