Codeforces Round #305 (Div. 2) D.Mike and Feet

D. Mike and Feet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.
A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.
Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.
Input
The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.
The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.
Output
Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.
Examples
input

10
1 2 3 4 5 4 3 2 1 6

output

6 4 4 3 3 2 2 1 1 1

참고:http://blog.csdn.net/libin56842/article/details/46473803
제목의 뜻은 말하지 않겠다.자서에 단조로운 창고가 있는 비슷한 문제가 있는데 뇌구멍이 크지 않아서 O(n)방법을 생각하지 못했다.대신의 단조로운 창고 사고방식을 거울로 삼았지만 생각은 아직 투철하지 않다.
단조롭게 증가하는 창고를 구성함으로써 어떤 길이의 구간 내에서 가장 작은 값이 얼마나 큰지 판단하는 것이다.
먼저 node를 구성하면num는 창고에 들어갈 때 이 원소의 값을 나타내고width는 너비를 나타내며 창고 꼭대기에서 원소의 거리를 나타낸다.연속 구간의 최소값을 찾았을 때, 실제적으로 최소값을 찾았을 때, 왼쪽에서 오른쪽으로 확장할 수 있는 최장 거리를 찾았다.여기의width는 왼쪽으로 확장된 거리 (자신 포함) 를 표시하고, 오른쪽으로 확장된 거리는 퇴장할 때 계산 (즉while 순환 중의len) 합니다.
처리가 완료되면 업데이트되지 않은 점이 있을 수 있으므로 앞으로 업데이트합니다.
ans[i]=max(ans[i],ans[i+1])
여기의 이해가 완전하지 않아서 처음에 ans[i]=0을 방지하는 줄 알았는데 실제 상황에서 이것뿐만 아니라 ans[i]의 크기도 보장할 수 있다는 것을 발견하고 마지막에 의심을 품었다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3
const int N=200005;
const int mod=1e9+7;

struct node{
    int num,width;
    node() {};
    node(int _num,int _width):num(_num),width(_width) {}
};

stack s;
int a[N],ans[N];

int main(){
    int n,i,j;
    cin>>n;
    for (i=0; ians[ls]) {
                ans[ls]=k.num;
            }
            len+=k.width;
            s.pop();
        }
        s.push(node(a[i],len+1));
    }
    for (i=n-1; i>=1; i--) {
        ans[i]=max(ans[i],ans[i+1]);
    }
    for (i=1; i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형

구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Codeforces Round #305 (Div. 2) D.Mike and Feet

좋은 웹페이지 즐겨찾기