笔试专题（十二）

主持人调度

题目链接

题解

1. 排序
2. 先按左端点的大小进行排序，保证时间是连续的，如果后一个点的左端点大于等于前一个点的右端点就是和法的，否则就不合法

代码

class Solution 
{
public:bool hostschedule(vector<vector<int>>& s) {// 按照左端点排序// 这个二维的数组是按左端点排序的sort(s.begin(),s.end());// 排序为了保证时间段时连续的// 二维的vector是先按第一个元素排序,再按第二个元素排序的int k = s[0][1];int p = 0,q = 0;int n = s.size(),m = 2;for(int i = 1;i < n;i++){for(int j = 0;j < m;j++){if(j == 0) p = s[i][j];// 左端点if(j == 1) q = s[i][j];// 右端点}if(p >= k){k = q;}else {return false;}}return true;}
};

小红的ABC

题目链接

题解

1. 找规律
2. 最短就是2或者3的情况，其他情况的子集也是2或者3

代码

#include<iostream>
#include<string>
using namespace std;int main()
{string s;cin >> s;int n = s.size();int ans = -1;// 没有回文子串for(int i = 0;i < n;i++){if(i + 1 < n && s[i] == s[i+1]){ans = 2;break;}if(i + 2 < n && s[i] == s[i+2]){ans = 3;}}cout << ans << '\n';return 0;
}

不相邻取数

题目链接

题解

1. 动态规划，线性dp
2. 类似于打家劫舍问题，简单多状态，一个位置选或者不选

代码

#include <iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 10;
int a[N];
int f[N];
int g[N];int main()
{int n;cin >> n;for(int i = 0;i < n;i++) cin >> a[i];f[0] = a[0];for(int i = 1;i < n;i++){f[i] = a[i] + g[i-1];g[i] = max(g[i-1],f[i-1]);}cout << max(f[n-1],g[n-1]) << '\n';return 0;
}

空调遥控

题目链接

题解

1. 排序 + 二分
2. 先枚举温度，最小的温度到最大的温度，再写出该温度的范围是k+p和k-p是符合要求的区间，再用二分查找找到左端点的下标和右端点的下标+1即是此次温度的最多人数，最后求最多的人数
3. 滑动窗口 + 排序
温度的范围是[t - p,t + p]，那么一定存在一个区间内的最大数 - 最小数 <= 2 * p，求区间的最长的长度

代码

// 排序 + 二分 O(n*logn + n*logn)
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e6 + 10;
int a[N];
int p,n;int main()
{cin >> n >> p;for(int i = 0;i < n;i++) cin >> a[i];// 排序 + 二分sort(a,a + n);int b = a[0],c = a[n-1];int ans = 0;// 枚举温度for(int i = b;i <= c;i++){int left = 0,right = n-1;int t1 = i + p;int t2 = i - p;int p1 = 0,p2 = 0;while(left < right){int mid = left + (right - left) / 2;if(a[mid] >= t2) right = mid;else{left = mid + 1;    }}p1 = left;left = 0,right = n - 1;while(left < right){int mid = (left + right + 1) / 2;if(a[mid] <= t1) left = mid;else right = mid - 1;}p2 = left;ans = max(ans,p2-p1 + 1);}cout << ans << '\n';return 0;
}// 滑动窗口 + 排序 O(n*logn + n)
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e6 + 10;
int a[N];int main()
{int n,p;cin >> n >> p;for(int i = 0;i < n;i++) cin >> a[i];sort(a,a+n);// 区间小于等于2pint k = 2 * p;int left = 0,right = 0;int ans = 0;while(right < n){while(a[right] - a[left] > k){left++;}if(a[right] - a[left] <= k) ans = max(ans,right - left + 1);right++;}cout << ans << '\n';return 0;
}