C 解法, 执行用时: 21ms, 内存消耗: 1668K, 提交时间: 2021-07-04 09:42:31
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[50005],v1[50005],v2[50005];
int st[50005],h,r;
int main(){
int t,i,n,ca=0,tmp,s,c,c1;
h=0;
r=0;
scanf("%d",&t);
while(t--){
r=0;
ca++;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
for(i=1;i<=n;i++){
tmp=0;
v1[i]=v1[i-1];
while(r!=0&&st[r]<a[i]){
r--;
tmp++;
}
if(r!=0) v1[i]+=tmp+1;
else v1[i]+=tmp;
r++;
st[r]=a[i];
}
r=0;
for(i=n;i>=1;i--){
tmp=0;
v2[i]=v2[i+1];
while(r!=0&&st[r]<a[i]){
r--;
tmp++;
}
if(r!=0) v2[i]+=tmp+1;
else v2[i]+=tmp;
r++;
st[r]=a[i];
}
s=0;
c=0;
for(int s1=2;s1<=n;s1++){
c1=v1[n]-(v1[s1-1]+v2[s1]);
if(c1>c){
c=c1;
s=s1;
}
}
printf("Case #%d: %d %d\n",ca,s,c);
}
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 189ms, 内存消耗: 41460K, 提交时间: 2022-11-29 18:58:07
T = int(input())
for t in range(T):
n = int(input())
a = list(map(int, input().split()))
s, p, cur = [], [], 0
for i in a:
while s and s[-1] < i:
cur += 1
s.pop()
if s: cur += 1
p.append(cur)
s.append(i)
m = cur
s, q, cur = [], [], 0
for i in reversed(a):
while s and s[-1] < i:
cur += 1
s.pop()
if s: cur += 1
q.append(cur)
s.append(i)
q = q[::-1]
# print(p, q)
idx, ans = 0, 0x7fffffff
for i in range(n-1):
cur = p[i]+q[i+1]
if cur < ans:
idx, ans = i, cur
print("Case #{}: {} {}".format(t+1, idx+2, m-ans))
C++11(clang++ 3.9) 解法, 执行用时: 34ms, 内存消耗: 1892K, 提交时间: 2019-04-07 16:08:14
#include <bits/stdc++.h>
using namespace std;
int t, n, x;
int z[50001];
int main() {
scanf("%d", &t);
for (int tt = 1; tt <= t; tt++) {
stack<pair<int, int> > s;
scanf("%d", &n);
memset(z, 0, sizeof z);
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
while (s.size() > 0 && x >= s.top().first) {
z[s.top().second]++;
z[i]--;
s.pop();
}
if (s.size() > 0) {
z[s.top().second]++;
z[i]--;
}
s.push(make_pair(x, i));
}
int p = 0;
for (int i = 1; i <= n; i++) {
z[i] += z[i - 1];
if (z[p] < z[i]) {
p = i;
}
}
printf("Case #%d: %d %d\n", tt, p + 1, z[p]);
}
}
时，这两个哨兵可以相互监视，M国的防守能力大小为相互监视的哨兵对数。H国早已对M国虎视眈眈，H国的皇帝希望黑魔法师们可以在M国的某两座山之间放置一块巨大的屏障,M国的哨兵不可通过该屏障互相监视。皇帝想让你告诉他最优的屏障放置位置，你是皇帝手下最信任的军师，现在需要你帮助皇帝计算最优的屏障放置位置和最大的防守力减少量。