B. Hills And Valleys
數學 暴力
- 題設：T個樣例下，每個樣例輸入n，和長度為n的序列a【i】各位的值，
定義：當j (2 ≤ j ≤ n?1)時，若 a[j] > a[j+1] 且 a[j] > a[j?1] 則稱這點位波峰，若 a[j] < a[j+1] 且 a[j] < a[j?1] 則稱這點為波谷，
現可對序列中任意一個位置的值修改，問改動一次后，整個序列中波峰和波谷的總數，最少是多少， - 思路： 計算改動前的峰谷總數是多少后，單個for回圈加特判可解決此問題，
簡單的“心電圖”，操作無非就是兩種：
要么把a【i】變成 a【i+1】，要么把a【i+1】變成 a【i】，
但是在這里，A邊和E邊是否存在，會影響到改變后是否會出現新的峰/谷，此時B，C，D的大小又有抵消這個影響的可能，
此題的坑點就是：消去兩個峰/谷的情況只有四種，
要解決的就是六點五邊之間的各種關系，五條邊分別命名為A，B，C，D，E，基本圖示如下，
-
連著三個點都是峰/谷的時候，無論五條邊的長度如何，此時都可以對中間點處理消去三個峰/谷，這也是最好的情況，
-
B >= C，此時可以消去兩個峰/谷，
-
D >= C，此時也可消去兩個峰/谷，
-
A == 0 或 E == 0的情況，可消去兩個峰/谷，
-
構不成六點五邊的時候，即在序列的兩端時，i ==2 或者 i ==n-2，可消去兩個峰/谷，（兩種情況都可用此圖表示）
注意，僅僅是兩個峰/谷相鄰，但是2，3，4，5四個條件均不滿足時，即此時B<C，D<C，A!=0且E!=0，i!=2且i!=n-2，此時無論怎么變化，都會出現一個新的峰/谷，則最多消去一個，
簡單畫圖示意即可明白文章開頭說的，什么是“A和E的影響”，什么又是“B，C，D可抵消這種影響”，
AC代碼：
#include<bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > QM;
const int INF= 0x3f3f3f3f;
const int maxn= 3e5+5;
int a[maxn],vis[maxn];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=n+1;i++) vis[i] =0;
int ans=0,cnt=0;
for(int i=2;i<=n-1;i++)
{
if(a[i]>a[i-1] && a[i]>a[i+1]) vis[i]=1,ans++;
if(a[i]<a[i-1] && a[i]<a[i+1]) vis[i]=1,ans++;
}
if(ans!=0) cnt=1;
for(int i=2;i<=n-1;i++)
{
if(vis[i])
{
if(vis[i] && vis[i-1] && vis[i+1])
{
cnt=3;
break;
}
if(vis[i+1] && (i==2 || i==n-2))
cnt = 2;
if(vis[i+1] && abs(a[i-1]-a[i])>=abs(a[i+1]-a[i]))
cnt = 2;
if(vis[i+1] && abs(a[i+2]-a[i+1])>=abs(a[i]-a[i+1]))
cnt = 2;
if(vis[i+1] && (a[i-2]==a[i-1] || a[i+2]==a[i+3]))
cnt = 2;
}
}
cout<<ans-cnt<<endl;
}
int main()
{
IOS;
int t;cin>>t;
while(t--){ solve(); }
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246989.html
標籤：其他
上一篇：QPSK調制解調Matlab實作