廊坊网站建,赣州做网站的,哈尔滨在线制作网站,莱芜在线论坛莱芜一中李念学相差不超过k的最多数
链接:相差不超过k的最多数 来源#xff1a;牛客网
题目描述#xff1a;
给定一个数组#xff0c;选择一些数#xff0c;要求选择的数中任意两数差的绝对值不超过 #x1d458; 。问最多能选择多少个数#xff1f;
输入描述:
第一行输入两个正整…相差不超过k的最多数
链接:相差不超过k的最多数 来源牛客网
题目描述
给定一个数组选择一些数要求选择的数中任意两数差的绝对值不超过 。问最多能选择多少个数
输入描述:
第一行输入两个正整数 和。 第二行输入 个正整数 用空格隔开表示这个数组。
输出描述:
一个正整数代表能选的最多数量。 数据范围1≤≤2×105 1≤,≤1091≤k,
示例1
输入 5 3 2 1 5 3 2 输出 4
说明 显然1和5不能同时选。所以最多只能选4个数。
算法原理
双指针
代码
#include iostream
using namespace std;
#include vector
#include functional
int main() {int n,k;cinnk;vectorint a(n,0);for(int i 0;in;i)cina[i];sort(a.begin(),a.end());// for(auto e:a)// coute ;int left 0;int len 0;for(int right 0;rightn;right){if(a[right]-a[left]k){len max(len,right-left);//coutleft:rightendl;left;while(a[right]-a[left]k)left;}len max(len,right-left1);}coutlen;return 0;
}最长公共子序列(一)
链接:最长公共子序列(一)
算法原理
动态规划
代码
#include iostream
using namespace std;
#include vector
int main() {int n,m;cinnm;string s1,s2;cins1s2;s1 s1;s2 s2;vectorvectorint dp(n1,vectorint(m1,0));for(int i 1;in;i){for(int j 1;jm;j){if(s1[i]s2[j])dp[i][j] dp[i-1][j-1]1;else{dp[i][j] max(dp[i-1][j],dp[i][j-1]);}}}coutdp[n][m];return 0;
}排序子序列
链接:排序子序列
算法原理
贪心模拟
代码
#include iostream
using namespace std;
#include vector
int main() {int n;cinn;vectorint arr(n,0);for(int i 0;in;i){cinarr[i];}int count 0;int cur 1;while(curn){//跳过相等的while(arr[cur]arr[cur-1]){cur;}if(curnarr[cur]arr[cur-1]){while(curnarr[cur]arr[cur-1]){cur;}count;cur;}if(curnarr[cur]arr[cur-1]){while(curnarr[cur]arr[cur-1])cur;cur;count;}//如果只有最后一个元素if(curn)count;}coutcountendl;return 0;
}体操队形
链接:体操队形 算法原理
dfs/递归 决策树
代码
#include iostream
using namespace std;
#include vector
int n;
vectorint a;
vectorbool vis;
vectorint path {0};
int count 0;
void dfs(int pos)
{if(posn){count;return;}for(int i 1;in;i){//判断是否满足位置要求if(vis[i](vis[a[i]]false||a[i]i)){vis[i] false;dfs(pos1);vis[i] true;}}
}
int main()
{cinn;vis.resize(n1,true);a.resize(n1,0);for(int i 1;in;i) cina[i];dfs(1);coutcountendl;return 0;
}[蓝桥杯 2022 省 A] 青蛙过河
题目描述
小青蛙住在一条河边它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线小青蛙每次跳跃必须落在一块石头或者岸上。不过每块石头有一个高度每次小青蛙从一块石头起跳这块石头的高度就会下降 1 1 1当石头的高度下降到 0 0 0 时小青蛙不能再跳到这块石头上某次跳跃后使石头高度下降到 0 0 0 是允许的)。
小青蛙一共需要去学校上 x x x 天课所以它需要往返 2 x 2x 2x 次。当小青蛙具有一个跳跃能力 y y y 时它能跳不超过 y y y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x x x 次课。
输入格式
输入的第一行包含两个整数 n , x n, x n,x, 分别表示河的宽度和小青蛙需要去学校的天数。请注意 2 x 2x 2x 才是实际过河的次数。
第二行包含 n − 1 n-1 n−1 个非负整数 H 1 , H 2 , ⋯ , H n − 1 H_{1}, H_{2}, \cdots, H_{n-1} H1,H2,⋯,Hn−1, 其中 H i 0 H_{i}0 Hi0 表示在河中与 小青蛙的家相距 i i i 的地方有一块高度为 H i H_{i} Hi 的石头 H i 0 H_{i}0 Hi0 表示这个位置没有石头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例 #1
样例输入 #1
5 1
1 0 1 0样例输出 #1
4提示
【样例解释】
由于只有两块高度为 1 1 1 的石头所以往返只能各用一块。第 1 1 1 块石头和对岸的距离为 4 4 4如果小青蛙的跳跃能力为 3 3 3 则无法满足要求。所以小青蛙最少需要 4 4 4 的跳跃能力。
【评测用例规模与约定】
对于 30 % 30 \% 30% 的评测用例 n ≤ 100 n \leq 100 n≤100;
对于 60 % 60 \% 60% 的评测用例 n ≤ 1000 n \leq 1000 n≤1000;
对于所有评测用例 1 ≤ n ≤ 1 0 5 , 1 ≤ x ≤ 1 0 9 , 0 ≤ H i ≤ 1 0 4 1 \leq n \leq 10^{5}, 1 \leq x \leq 10^{9}, 0 \leq H_{i} \leq 10^{4} 1≤n≤105,1≤x≤109,0≤Hi≤104 。
蓝桥杯 2022 省赛 A 组 F 题。
算法原理
借鉴的别人的解法这里讲一下思路 将问题转换为2x只青蛙过河的问题 这个解析是站在已知最小y的情况下推的一些性质然后用这些性质来结算y
代码
#include iostream
using namespace std;
#include vectorint main()
{int n,x;cinnx;int val;vectorint v(1,0);while(cinval){v.push_back(val);}int right 1,left 1;int sum 0;int y 0;for( ;rightv.size();right){sumv[right];if(sum2*x){y max(y,right-left1);sum-v[left];while(sum2*x){sum-v[left];}}}if(y0){coutn;}else{couty;}return 0;
}
