【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);}
}