主持人調度

題目鏈接

題解

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