Antinomy与法术威力

NC231161. Antinomy与法术威力

描述

一天Antinomy正在练习魔法，他将 $\mathit n$ 个魔法咒语排成一排，每个咒语都拥有一个威力值 $\mathit a_i$

一个魔法是一串非空连续的魔法咒语构成，一个魔法的施法时间就是咒语的数量，一个魔法的威力就是该魔法中咒语的最小威力值

Antinomy很好奇，对于相同的施法时间 $x(1 ≤ x ≤ n)$ ,魔法的最大威力是多少，从 $x = 1$ 开始输出

输入描述

第一行一个整数 $n(1≤ n ≤200000)$ --一共有 $\mathit n$ 个魔法咒语。

第二行n个整数 $a_1,a_2...a_n(1≤ a_i ≤200000)$ ,其中 $\mathit a_i$ 是 $\mathit i$ 个咒语的威力值。

输出描述

在一行中输出个整数。从到，输出相同施法时间的魔法最大威力值

示例1

输入:

5
3 7 7 2 4

输出:

7 7 3 2 2

说明:

施放时间x=1魔法最大威力的子数组是[7]

施放时间x=2魔法最大威力的子数组是[7,7]

施放时间x=3魔法最大威力的子数组是[3,7,7]

施放时间x=4魔法最大威力的子数组是[3,7,7,2],[7,7,2,4]

施放时间x=5魔法最大威力的子数组是[3,7,7,2,4]

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 64ms, 内存消耗: 2552K, 提交时间: 2022-03-26 16:54:57

#include<bits/stdc++.h>
using namespace std;
const int N=200000+5;

int n,a[N],dp[N];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		while(l>=1&&a[l]>=a[i]) l--;
		while(r<=n&&a[r]>=a[i]) r++;
		int w=r-l-1;
		dp[w]=max(dp[w],a[i]);
	}
	for(int i=n;i>=1;i--){
        if(dp[i]<dp[i+1]) dp[i]=dp[i+1];
    }
    for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
	return 0;
}

上一题

下一题

详情