感觉太巧妙了吧…怎么也想不到
开始一直以为是树状数组什么的…没想到是思维题
用 d p [ x ] 数 组 维 护 删 除 后 对 整 个 序 列 的 r e c o r d 数 量 用dp[x]数组维护删除后对整个序列的record数量 用dp[x]数组维护删除后对整个序列的record数量
设 当 前 第 i 个 数 字 是 a i , 假 如 a i 既 不 是 最 大 也 不 是 次 大 那 么 压 根 不 用 管 设当前第i个数字是a_i,假如a_i既不是最大也不是次大那么压根不用管 设当前第i个数字是ai,假如ai既不是最大也不是次大那么压根不用管
因 为 删 掉 前 面 的 任 意 一 个 数 不 可 能 使 a i 变 成 r e c o r d \color{Red}因为删掉前面的任意一个数不可能使a_i变成record 因为删掉前面的任意一个数不可能使ai变成record
删 掉 a i 不 会 使 后 面 的 数 字 成 为 r e c o r d \color{Red}删掉a_i不会使后面的数字成为record 删掉ai不会使后面的数字成为record
那 么 当 a i 是 [ 1 , i ] 最 大 的 , 删 掉 a i 使 序 列 r e c o r d 减 去 1 , d p [ a i ] − − 那么当a_i是[1,i]最大的,删掉a_i使序列record减去1,dp[a_i]-- 那么当ai是[1,i]最大的,删掉ai使序列record减去1,dp[ai]−−
当 a i 是 次 大 的 , 删 掉 [ 1 , i ] 的 最 大 值 使 a i 成 为 r e c o r d , d p [ m a x ] + + 当a_i是次大的,删掉[1,i]的最大值使a_i成为record,dp[max]++ 当ai是次大的,删掉[1,i]的最大值使ai成为record,dp[max]++
#include <bits/stdc++.h> using namespace std; const int maxn=3e5+10; int dp[maxn],n,x,max1,max2; int main() { cin>>n; for(int i=1;i<=n;i++) { cin >> x; //x是当前最大值,若去掉x对[1,i]的贡献是-1 if(x>max1) dp[x]--,max2=max1,max1=x; //x是次大值,那么去掉[1,i]的最大值可以让x变成最大值 else if(x>max2) dp[max1]++,max2=x; } int ans=1; for(int i=1;i<=n;i++) if(dp[i]>dp[ans]) ans=i; cout<<ans; return 0; }