笔试专题（十六）

相差不超过k的最多数

题目链接

题解

1. 排序 + 滑动窗口
2. 为什么使用滑动窗口？
因为max-min <= k，求这个区间内的数最多，不定长的滑动窗口，可能中间的数最多，两边的数最多，所以让区间移动
3. 为何滑动窗口合法？
出窗口的时候我们是不确定left指针是否符合窗口，可能让left多次出窗口，第一个窗口中间的数依旧合法，因为一个大的数减一个小的数合法，依旧是这个大的数减比原先更大的数肯定也是合法的，所以不需要回退right指针，因此用滑动窗口

代码

#include <iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 10;
int a[N];int main()
{int n,k;cin >> n >> k;for(int i = 0;i < n;i++) cin >> a[i];int l = 0,r = 0;int ret = 0;sort(a,a+n);// 为什么使用滑动窗口,让最小值和最大值 <= k,区间就是满足要求的// 中间可能有奇怪的区间满足最大的区间,二两边的数不满足,让区间去移动,找最大的区间while(r < n){while(a[r] - a[l] > k){l++;} ret = max(ret,r - l + 1);r++;}cout << ret << '\n';return 0;
}

最长公共子序列（一）

题目链接

题解

1. 动态规划
2. 状态表示：s1在[0,i]区间内以及s2[0,j]区间内，所有的子序列里面，最长公共子序列的长度
3. 状态转移方程：
如果最后一个位置s1[i] = s2[j]，那么就是前面的子序列加上最后一个位置的长度
如果最后一个位置s1[i] != s2[j]，那么可能是s1的[0,i-1]和s2的[0,j]中的最长公共子序列和s1的[0,i]和s2的[0,j-1]的最长公共子序列中的最大值

代码

class Solution 
{
public:int LCS(string s1, string s2) {int m = s1.size();int n = s2.size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);}}return dp[m][n];}
};

小红的口罩

题目链接

题解

1. 贪心 + 小根堆
2. 每次选择最小的不舒适度，可以让让不舒适度缓慢增长，不超过k，可以让天数尽可能的大

代码

#include<iostream>
#include<queue>
using namespace std;const int N = 1e5 + 10;
int a[N];int main()
{// 小根堆priority_queue<int,vector<int>,greater<int>> pq;int n,k;cin >> n >> k;for(int i = 0;i < n;i++){cin >> a[i];pq.push(a[i]);}int day = 0;while(k){int t = pq.top();if(k - t >= 0){k -= t;day++;pq.pop();t *= 2;pq.push(t);}else break;}cout << day << '\n';return 0;
}

春游

题目链接

题解

1. 贪心 + 分情况讨论

代码

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;int main()
{int t;cin >> t;while(t--){LL n,a,b;cin >> n >> a >> b;LL ans = 0;if(n <= 2) {if(a < b) cout << a << '\n';else cout << b << '\n';continue;}// 双人船if(3*a < 2*b){int k = n / 2;ans += k * a;if(n % 2 == 1){ans += min(min(a,b),(b-a));}}else if(3*a > 2*b){// 三人船int k = n / 3;ans += k * b;if(n % 3 == 1){ans += min(2*a-b,min(a,b));}else if(n % 3 == 2){ans += min((3*a-b),min(a,b));}}cout << ans << '\n';}return 0;
}