娱乐网站 建站软件,阿里云网站用什么做的,网站百度地图标记代码,福州网站建设找百诚互联目录 不相邻取数#xff08;动态规划-线性dp#xff09;
题目解析
讲解算法原理
编写代码
空调遥控#xff08;⼆分/滑动窗⼝#xff09;
题目解析
讲解算法原理
编写代码 不相邻取数#xff08;动态规划-线性dp#xff09;
题目解析
1.题目链接#xff1a;不相…目录 不相邻取数动态规划-线性dp
题目解析
讲解算法原理
编写代码
空调遥控⼆分/滑动窗⼝
题目解析
讲解算法原理
编写代码 不相邻取数动态规划-线性dp
题目解析
1.题目链接不相邻取数_牛客题霸_牛客网
2.题目描述 描述 小红拿到了一个数组。她想取一些不相邻的数使得取出来的数之和尽可能大。你能帮帮她吗 输入描述 第一行输入一个正整数 n\n 代表数组长度 第二行输入 n\n 个正整数 a_iai 代表整个数组。 1 \leq n \leq 2*10^5 , 1\leq a_i \leq 5*10^31≤n≤2∗105,1≤ai≤5∗103 输出描述 不相邻的数的最大和。 示例1 输入 4 2 6 4 1 输出 7 说明 取 6 和 1 即可 讲解算法原理
解法 算法思路 打家劫舍~
编写代码
c算法代码
#include iostream
using namespace std;
const int N 2e5 10;
int n;
int arr[N];
int f[N], g[N];
int main()
{cin n;for(int i 1; i n; i) cin arr[i];for(int i 1; i n; i){f[i] g[i - 1] arr[i]; g[i] max(f[i - 1], g[i - 1]); }cout max(f[n], g[n]) endl;return 0;
}
java算法代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in new Scanner(System.in); int n in.nextInt();int[] arr new int[n 1]; int[] f new int[n 1]; int[] g new int[n 1];for(int i 1; i n; i){arr[i] in.nextInt();}for(int i 1; i n; i){f[i] g[i - 1] arr[i]; g[i] Math.max(f[i - 1], g[i - 1]); }System.out.println(Math.max(f[n], g[n]));}
}
空调遥控⼆分/滑动窗⼝
题目解析
1.题目链接登录—专业IT笔试面试备考平台_牛客网
2.题目描述 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 题目描述 dddddd作为集训队的队长一直掌管着集训室的空调遥控器她需要调整温度使队员们更好地进入训练状态已知集训室一共有nnn名队员每位队员都有一个温度诉求a[i](1≤i≤n)a[i](1≤i≤n)a[i](1≤i≤n)当室内温度为KKK时当且仅当∣a[i]−K∣≤p|a[i]-K|≤p∣a[i]−K∣≤p时这个队员能够正常进入训练状态否则就会开始躁动作为队长dddddd需要调整好温度她想知道在最佳情况下最多有多少队员同时进入训练状态 输入描述: 第一行两个数n,p(1≤n,p≤1000000),含义如题面描述 接下来一行n个数a[i](1≤a[i]≤1000000)表示每个队员的温度诉求 输出描述: 输出一个数字表示最多有多少队员同时进入训练状态 示例1 输入 6 2 1 5 3 2 4 6 6 2 1 5 3 2 4 6 输出 5 5 讲解算法原理
解法 算法思路 先排序。 解法⼀滑动窗⼝ 维护窗⼝内最⼤值与最⼩值的差在 2 * p 之间。 解法⼆⼆分查找 枚举所有的温度⼆分出符合要求的学⽣区间然后统计个数。
编写代码
c算法代码
#include iostream
#include algorithm
using namespace std;
const int N 1e6 10;
int n, p;
int arr[N];
int main()
{cin n p;for(int i 0; i n; i) cin arr[i]; sort(arr, arr n);int ret 0, left 0, right 0; p * 2;while(right n){while(arr[right] - arr[left] p){left;}ret max(ret, right - left 1); right;}cout ret endl;return 0;
}
java算法代码
import java.util.*;
public class Main
{public static void main(String[] args){Scanner in new Scanner(System.in); int n in.nextInt(), p in.nextInt(); int[] arr new int[n]; for(int i 0; i n; i){arr[i] in.nextInt();}Arrays.sort(arr);int left 0, right 0, ret 0; p * 2; while(right n){while(arr[right] - arr[left] p){left;}ret Math.max(ret, right - left 1); right;}System.out.println(ret);}
}
