2020年10月安徽省省賽
C. 前后相加
給定一個序列，長度為 N，開始時，上面所有元素為 0。
你可以對序列作如下兩種操作：
1.指定一個整數 k（1<=k<=N）和一個非降序列 c1,c2,c3,…,ck，（ci 非負，
1<=i<=k），對序列 x 的前 k 個數，令 xi=ci+xi。
2.指定一個整數 k（1<=k<=N）和一個非升序列 c1,c2,c3,…,ck，（ci 非負，
1<=i<=k），對序列 x 的后 k 個數，令 x[N-k+i]=ci+x[N-k+i]。
你的目標是將序列 x 構造為與序列 A 相等的序列，即 xi=Ai(1<=i<=n)，輸出
最少需要多少此操作，以達成目標。
資料范圍
1 ≤ ?N≤ 2 ? 10^5
1≤Ai ≤ 10^9
輸入說明
第一行為一個整數 N，序列的長度。
第二行為 N 個整數，表示目標序列 A。
輸出說明
輸出最少的操作次數。
樣例一
輸入
5
1 2 1 2 1
輸出
3
5
樣例二
輸入
5
2 1 2 1 2
輸出
2
解題思路：
猜測是結論題，大部分情況的答案是2、3。
具體解法：
首先答案為1的情況下只有陣列的前綴（后綴）遞增或者遞減，所以可以對答案為1的情況進行特判。
答案為2的情況下可以出現很多種不同的情況，猜測是最小值出現的次數。
代碼實作：
#include<bits/stdc++.h>///萬能頭檔案
using namespace std;
#define int long long
const int maxn = 1e3 + 10;
int n;
int a[maxn];
signed main()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++){
cin >> a[i];
}
bool ok = true;
for(int i = 1 ; i <= n ; i ++){
if(a[i] > a[i - 1]){
ok = false;
break;
}
}
if(ok){
cout << "1\n";
return 0;
}
ok = true;
for(int i = 2 ; i <= n ; i ++){
if(a[i] < a[i - 1]){
ok = false;
break;
}
}
if(ok){
cout << "1\n";
return 0;
}
int minn = 1e9 + 1;
for(int i = 2 ; i <= n ; i ++){
minn = min(minn , a[i]);
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
if(a[i] == minn) ans ++;
}
cout << ans << '\n';
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/239339.html
標籤：C++ 語言
上一篇：C語言怎么打開、讀和寫檔案
下一篇：各位大佬，幫忙看看唄