藍橋杯 1210. 連号區間數

文章目錄

• • • 1210. 連号區間數

AcWing網站原題通道

1210. 連号區間數

題意分析：給我們1~N的排列，讓我們求出這個排列中有多少個連号區間，，連号區間也就是對這個區間排序之後，相鄰兩數相差為1。先分析資料範圍有105，那麼我們可以使用時間複雜度為O(nlongn)的算法，如果想不出來可以考慮O(n2)的算法。

我們先來理一下暴力的思路：

for(枚舉起點)
	for(枚舉終點)
	{
		sort(); // 對起點和終點之間的區間排序
		chekc(); // 再次周遊檢查相鄰兩數的內插補點是否為1
	}
           

對于上邊暴力的做法，我們發現枚舉起點和終點這步很難去優化，那麼我們就可以考慮對判斷是否是連号區間這部操作來進行優化。

我們先來找一下連号區間的性質：

題目說給我們的是

1~N

的排列，那麼

1~N

之間的數肯定會不重不漏，那麼如果我們要判斷一個區間是否是連号區間，我們隻需要判斷這個區間裡邊最大值和最小值的差是否等于區間長度-1，如果等于就是連号區間；否則就不是。

舉個例子：

（1）對于132來說，這個區間最大值3，最小值1，區間長度-1為2， max-min == 2 ，是以是連号區間

（2）對于142來說，這個區間最大值是4，最小值是1，區間長度-1為2 ， max - min = 3 ， 不等于區間長度-1，是以不是連号區間

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010 , INF = 1e8;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    int res = 0;
    
    for(int i = 0; i < n; i++)
    {
        // 定義最大值和最小值
        int maxv = -INF , minv = INF;
        for(int j = i; j < n; j++)
        {
            maxv = max(maxv , a[j]);
            minv = min(minv , a[j]);
            // 判斷是否是連号區間
            if(maxv - minv == j-i) res ++;
        }
    }
    
    cout << res << endl;
    
    return 0;
}