【c++笔试强训】（第三十八篇）
目录
不相邻取数（动态规划-线性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);}
}