小a的排列（C++）
點擊做題網站鏈接
題目描述
小a有一個長度為n的排列。定義一段區間是"萌"的，當且僅當把區間中各個數排序后相鄰元素的差為1現在他想知道包含數x,y的長度最小的"萌"區間的左右端點
也就是說，我們需要找到長度最小的區間[l,r]，滿足區間[l,r]是"萌"的，且同時包含數x和數y
如果有多個合法的區間，輸出左端點最靠左的方案。
輸入描述:
第一行三個整數N,x,y，分別表示序列長度，詢問的兩個數
第二行有n個整數表示序列內的元素，保證輸入為一個排列
輸出描述:
輸出兩個整數，表示長度最小"萌"區間的左右端點
示例1
輸入
5 2 3
5 2 1 3 4
輸出
2 4
說明
區間[2,4]={2,1,3}包含了2,3且為“萌”區間，可以證明沒有比這更優的方案
示例2
輸入
8 3 5
6 7 1 8 5 2 4 3
輸出
5 8
備注:
保證2?n?105,1?x,y?n2?n?10^5,1?x,y?n2?n?105,1?x,y?n
解題思路：
"萌"的條件就是l - r == max - min(區間長度等于區間內的最大值減最小值)
那么我們先在l到r的區間中求出最大值和最小值，然后再去找這個區間外面的但是值是最小值到最大值范圍中的數
所以我們只需要去模擬這個過程就好了，不斷的找l到r區間外面的數，不斷的更新最大值和最小值。
解題代碼：
#include <iostream>
#include <algorithm>
using namespace std;
int pre[100005];int main()
{ios::sync_with_stdio(0);int n,x,y;//序列長度，詢問的兩個數cin >> n >> x >> y;int l,r;//區間的左右端點for(int i=1;i<=n;++i){cin >> pre[i];if( pre[i]==x ) l = i;//如果輸入的數字和x一樣，用l記錄其位置if( pre[i]==y ) r = i;//如果輸入的數字和y一樣，用r記錄其位置}if( l>r ) swap(l,r);int xx = 0, yy = n+1;while( r-l!=xx-yy )//"萌"的條件就是r-l==max-min(區間長度等于區間內的最大值減最小值){for(int i=l;i<=r;++i)//l到r的區間中求出最大值和最小值{xx = max(xx, pre[i]);//最大值yy = min(yy, pre[i]);//最小值}for(int i=1;i<=n;++i)//再去找這個區間外面的但是值是最小值到最大值范圍中的數{if( pre[i]>yy && pre[i]<xx && i<l ) l = i;if( pre[i]>yy && pre[i]<xx && i>r ) r = i;}}cout << l << " " << r << endl;
}
