思路
插入屏障就是将一个区间分割成两个区间[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; }