题解 CF1147A 【Hide and Seek】

流绪 · 2020-02-10 19:00:01 · 题解

对于一个代币 他有三种选择:往左移,不动,往右移 那我们枚举每一个单元格,设代币放里面,然后看看三种操作哪几种能够使代币不被发现,就让答案 +1

怎么判断会不会被发现呢,只要移动过去的那一格在询问中最后一次出现早于原本那一格第一次出现就可以了,所以我们只要在枚举前预处理 minn 数组存第一次出现的时间,maxn 数组存最后一次出现的时间,然后就能在接下来的枚举中 O(1) 地判断会不会被发现啦

下面是 AC 代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x7f7f7f7f
using namespace std;
ll maxn[1000010],minn[1000010];
ll a[1000010];
int main()
{
    ios::sync_with_stdio(false);
    ll n,k;
    cin >> n >> k;
    memset(maxn,-1,sizeof(maxn));
    memset(minn,inf,sizeof(minn));
    for(ll i=1;i<=k;i++)
    {
        cin >> a[i];
        maxn[a[i]] = max(maxn[a[i]],i);
        minn[a[i]] = min(minn[a[i]],i);//记录a[i]号最早被问和最晚被问的时间 
    }   
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(i<1||i>n)
            continue;
        if(minn[i] > maxn[i-1]&&i>1)
            ans++;
        if(minn[i] > maxn[i+1]&&i<n)
            ans++;
        if(minn[i] > maxn[i])
            ans++;
    }
    cout << ans;
}