当前位置: 首页 > news >正文

22 LCA模拟赛2T1 奶龙与贝利亚 题解

奶龙与贝利亚

题面

\(n\) 个生物排成一排,每个生物是奶龙或者贝利亚。

给定数组 \(a_1,a_2, \cdots, a_n\),有约束:

  • 若第 \(i\) 个位置是奶龙,那么前面恰好有 \(a_i\) 个奶龙。
  • 若第 \(i\) 个位置是贝利亚,那么前面至多有 \(a_i\) 个奶龙。

\(1 \le n \le 2 \times 10^5 , 0 \le a_i \le n\)

题解

这唐题在考场上给我暴击了。

对于放奶龙的这个约束,其实是挺强的,我们也不难发现,把放奶龙的 \(a_i\) 拎出来,会形成一个 \(0,1,\cdots\) 的序列。

如果只是这样的话,那就是最长上升子序列,但是这道题还有贝利亚的约束。

手模一下样例:0 1 2 0 1

发现最多只能在最后两个位置放两只奶龙,对于 \(a_i\) 相同的位置,我们只能选最后的一个放奶龙,否则后面就放不了贝利亚了。

那么思路就很简单了,对于每个 \(a_i\) 我们记录它最后出现的位置。

然后从小到大枚举 \(a_i\) ,记录上一个奶龙的位置,如果当前 \(pos > last\) 那就放,否则就再也放不了了。

时间复杂度 \(O(n)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>using namespace std;namespace michaele {const int N = 2e5 + 10;int n;int pos[N];void solve () {cin >> n;for (int i = 1; i <= n; i ++) {int x;cin >> x;pos[x] = i;}int la = 0;for (int i = 0; i < n; i ++) {if (pos[i] > la) {ans ++;la = pos[i];} else {break;}}cout << ans << endl;}
}int main () {michaele :: solve ();return 0;
}
http://www.hskmm.com/?act=detail&tid=27754

相关文章:

  • 微软拼音输入法自定义短语批量导入导出工具(支持Windows 10/11)
  • AI风险管控新规应对系统抵抗关闭行为
  • BLDC中的Q15
  • 华为 AP hw_manage 离线管理 Wi-Fi 密码
  • 雪落 - L
  • 251009
  • Mybatis笔记
  • PluginMonitor - Typecho 插件监控工具
  • LibreChat-图文并茂手把手教你搭建自己的AI机器人 Step-by-step guide to building your own chatbot
  • NOISG 2025 Prelim
  • STM32 教程
  • 先进反应堆:BWRX-300
  • ch58x/ch59x系列芯片Indication添加
  • Lab 4 Challenge - Sum of Proper Elements
  • perl经典hash解决问题
  • LCR 129. 字母迷宫
  • Ignite3 竟然变成分布式数据库了!
  • NUIST 《程序设计基础》 实验1
  • 10.9总结
  • [MIT 6.828] Lab 1 C, Assembly, Tools, and Bootstrapping
  • WCH低功耗蓝牙系列芯片usb烧录故障排查
  • 使用docker构建.net api镜像及nginx反向代理 - binzi
  • 利用sprintf与snprintf巧妙实现数值变量转换为字符串型
  • Helmholtz-Gibbs自由能与熵弹性
  • 日志|电话号码的字母组合|子集|回溯
  • Docker实用篇(初识Docker,Docker的基本操作,Dockerfile自定义镜像,Docker-Compose,Docker镜像仓库) - a
  • ROIR 2023
  • Rust 的验证码图像识别系统设计与实现
  • 【题解】P12992 [GCJ 2022 #1C] Intranets
  • ysyx:pa3.1批处理系统