題意
https://vjudge.net/problem/CodeForces-1238C
您現在正在玩一個游戲，您初始在一個高度 h 的懸崖
懸崖沿壁高度為 1-h 的這些位置均有平臺，平臺有兩種狀態，被選中/不被選中，您可以認為只有被選中的平臺才出現在這個懸崖上且你可以站在上面，
初始時有 n 個平臺為被選中，保證平臺 h 被選中，您每次可以進行一個操作，不妨假設您當前站在平臺 x 處（此時平臺 x 一定被選中），即讓平臺 x 變成未被選中，而平臺x?1 變成相反的狀態，
您非常的脆弱，所以不能跌落超過2的高度，比如您可以從高度為3的平臺跌落到高度為1的平臺，但不能從高度為3的平臺跌落到地面
現在您想要回到地面，即高度為0
您可以使用一種魔力水晶，即其可以將任意一個平臺修改成指定的狀態，
現在希望您求出回到地面最少需要使用多少顆魔力水晶？
思路
題意簡單來說就是踩在選中的平臺可以按開關，使得緊挨著的下面那個平臺狀態反轉，不能連續跳超過2個平臺，
如果隔了很遠才有一個平臺，顯然可以按一次開關下降一格，因為下面那個平臺會由未選中反轉到選中，所以可以踩，我們一直這樣做，直到跳到選中的平臺的上一個，設此時位置為x，且x和x-1是有平臺的，下面的為x-1,x-2，
如果x-2有平臺，那么可以按x的開關，然后就跳到x-2了，
如果x-2沒有平臺，那么按了x的開關后，跳的距離肯定是大于2的了，因為x-1也識訓了平臺，這種情況就死了，需要一個水晶使得x-1的狀態先改為未選中，這樣就可以像開始說的那樣往下一步一步的跳，直到跳到有平臺的上一格，那么情況又和上面一樣了，
總結，除去第一個平臺（h），往下跳，每遇到兩個距離>1的平臺（x-1有平臺，x-2沒有平臺的情況），那么需要一個水晶，跳到x-2，否則就跳過這些平臺，跳到x-3平臺的上一格繼續考慮，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll p[N];
int main()
{
std::ios::sync_with_stdio(false);
int q;
cin>>q;
while(q--)
{
ll h,n;
cin>>h>>n;
for(int i=1;i<=n;i++)
cin>>p[i];
ll cnt=0;
p[n+1]=0;
for(int i=2;i<=n;i++)
{
if(p[i]-p[i+1]>1)
cnt++;
else i++;
}
cout<<cnt<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119218.html
標籤：其他
上一篇：通俗易懂的二分查找及其變體問題
下一篇：記錄第一次發動態