织梦网站备案,网站答辩ppt怎么做,个人网页制作素材图片,国家住房和城乡建设部官网小a的排列#xff08;C#xff09; 点击做题网站链接 题目描述 小a有一个长度为n的排列。定义一段区间是萌的#xff0c;当且仅当把区间中各个数排序后相邻元素的差为1现在他想知道包含数x,y的长度最小的萌区间的左右端点 也就是说#xff0c;我们… 小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 i1;in;i){cin pre[i];if( pre[i]x ) l i;//如果输入的数字和x一样用l记录其位置if( pre[i]y ) r i;//如果输入的数字和y一样用r记录其位置}if( lr ) swap(l,r);int xx 0, yy n1;while( r-l!xx-yy )//萌的条件就是r-lmax-min(区间长度等于区间内的最大值减最小值){for(int il;ir;i)//l到r的区间中求出最大值和最小值{xx max(xx, pre[i]);//最大值yy min(yy, pre[i]);//最小值}for(int i1;in;i)//再去找这个区间外面的但是值是最小值到最大值范围中的数{if( pre[i]yy pre[i]xx il ) l i;if( pre[i]yy pre[i]xx ir ) r i;}}cout l r endl;
}转载于:https://www.cnblogs.com/yuzilan/p/10626084.html
