[PA 2022] Ornitolog 2

题目描述

题目译自 PA 2022 Runda 1 Ornitolog 2

交替鹡鸰（Motacilla alterna）是鹡鸰属的一种鸟类。它因其独特的鸟鸣而与众不同，这种鸟的鸟鸣中，连续的音高交替地增加和减少。例如，如果我们用整数来表示音高，那么，鸟鸣可以是 $[2,1,3]$ 和 $[4,5,-6,-5]$，但不能是 $[1,2,3,2]$ 或 $[6,5,5,4]$。为了记录这种迷人的生物，鸟类学家 Byteasar 将他的录音笔留在森林中数天。他现在想知道录到的声音是否与鹡鸰的鸟鸣相似。

写一个程序，给定音高序列，确定最少将音高序列中多少个整数改成 $[-10^9,10^9]$ 区间内的任意整数，才能使得这个序列成为交替鹡鸰鸟鸣的音高序列。

输入格式

第一行一个整数 $n$，表示这个音高序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示这个音高序列。

输出格式

输出最少要修改多少整数才能使这个序列成为交替鹡鸰鸟鸣的音高序列。

样例 #1

样例输入 #1

5
4 1 3 3 1

样例输出 #1

1

样例 #2

样例输入 #2

4
-1000000 -1000000 -1000000 -1000000

样例输出 #2

2

提示

对于 $100\%$ 的数据，满足：

$3\le n\le 5\times 10^4,-10^6\le a_i\le 10^6$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i];b[i]=a[i];
}
int lh=0,hl=0;
for(int i=1;i<n;i++){
if(i%21&&a[i]>=a[i-1]||i%20&&a[i]<=a[i-1]){
hl++;
if(i%21) a[i]=-1e9;
else a[i]=1e9;
}
if(i%21&&b[i]<=b[i-1]||i%20&&b[i]>=b[i-1]){
lh++;
if(i%21) b[i]=1e9;
else b[i]=-1e9;
}
}
cout<<min(lh,hl);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容