Codeforces Round #656 (Div. 3) C. Make It Good
2024-09-07 13:32:27
题目链接:https://codeforces.com/contest/1385/problem/C
题意
去除一个数组的最短前缀使得余下的数组每次从首或尾部取元素可以排为非减序。
题解一
当两个大数夹着一个小数那么第一个大数及其之前的数必须要去掉,比如 $1,1,2,1,2$,要去除的前缀长为 $3$,但是考虑到也会有 $1,1,2,1,1,2$ 的情况,所以可以将原数组去重后判断每三个相邻的元素。
代码
#include <bits/stdc++.h>
using namespace std; void solve() {
int n; cin >> n;
int a[n] = {}; for (int i = 0; i < n; ++i) cin >> a[i];
vector<pair<int, int>> v;
for (int i = 0; i < n; ) {
int j = i + 1;
while (j < n and a[j] == a[i]) ++j;
v.emplace_back(a[i], j - 1);
i = j;
}
for (int i = v.size() - 1; i - 2 >= 0; --i) {
if (v[i - 2].first > v[i - 1].first and v[i - 1].first < v[i].first) {
cout << v[i - 2].second + 1 << "\n";
return;
}
}
cout << 0 << "\n";
} int main() {
int t; cin >> t;
while (t--) solve();
}
题解二
换言之,即找右端山脚为数组末尾元素的最长的山峰。
代码
#include <bits/stdc++.h>
using namespace std; void solve() {
int n; cin >> n;
int a[n] = {}; for (auto &i : a) cin >> i;
int p = n - 1;
while (p - 1 >= 0 and a[p - 1] >= a[p]) --p;
while (p - 1 >= 0 and a[p - 1] <= a[p]) --p;
cout << p << "\n";
} int main() {
int t; cin >> t;
while (t--) solve();
}
最新文章
- MinGW安装c-c++
- VC++模态对话框和非模态对话框
- portable runtime
- Moses manual 中Basline System 2.3.4节用IRSTLM创建语言模型的命令有误
- iis 下的 selfssl
- 转载的在DOS下操作mysql
- php 在web端读出pdf 与各种文件下载
- html5储存篇(二)
- 重拾linux
- Keyboard Row
- HashMap面试题:90%的人回答不上来
- 冒烟测试与BVT测试
- (7拾遗)从零开始的嵌入式图像图像处理(PI+QT+OpenCV)实战演练
- C#采用rabbitMQ搭建分布式日志系统
- 2017年总结的前端文章——border属性的多方位应用和实现自适应三角形
- 关于git post-receive 钩子
- Android开发——签名包的生成
- Javascript入门(三)函数
- 【工具相关】Web-将网站放在XAMPP上面
- 仿迅雷播放器教程 -- 基于ffmpeg的C++播放器 (1)