链接:https://ac.nowcoder.com/acm/contest/317/G
来源:牛客网
小a有一个长度为nn的排列。定义一段区间是"萌"的,当且仅当把区间中各个数排序后相邻元素的差为11
现在他想知道包含数x,yx,y的长度最小的"萌"区间的左右端点
#include<iostream> #include<algorithm> using namespace std; int n, x, y; int pre[100005]; int main() { int l, r; cin >> n >> x >> y; for (int i = 1; i <= n; ++i) { cin >> pre[i]; if (pre[i] == x)l = i; if (pre[i] == y)r = i; } if (l > r)swap(l, r); int xx = 0, yy = n + 1; while (r - l != xx - yy){ for (int i = l; i <= r; ++i){ 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; }
原文:https://www.cnblogs.com/ALINGMAOMAO/p/10327422.html