题解：P11551 [ROIR 2016 Day 1] 奖品

cff_0102 · 2025-01-10 14:13:45 · 题解

题意简述：求前缀次大值。

用两个变量 mx,mx2 记录目前的最大值和次大值。

• 如果新的数 x 大于等于原本的 mx，则将 mx2 替换为 mx 并将 mx 替换为 x；
• 否则，如果 x 大于等于原本的 mx2，则将 mx2 替换为 x。

每加一个数后就输出当前的 mx2。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int mx=0,mx2=0;
    cin>>mx;
    while(--n){
        int x;cin>>x;
        if(x>=mx)mx2=mx,mx=x;
        else if(x>=mx2)mx2=x;
        cout<<mx2<<" ";
    }
    return 0;
}