思路：
圖的周遊，若想總路程最小，将最大深度的路徑放在最後周遊
除去最大深度的路徑，其餘邊均需要周遊兩遍，是以
最短路徑 = 2*(n-1) - maxDepth (n-1)為邊的數量
代碼：
#include <iostream>
int depth[];
using namespace std;
int main(){
int n;
cin >> n;
for(int i=; i<n; i++){
int a, b;
cin >>a >> b;
depth[b] = depth[a] + ;//目前節點的深度
}
int maxDepth = ;
for(int i=; i<=n; i++)
maxDepth = depth[i]>maxDepth ? depth[i] : maxDepth;//尋找最大值
cout << *(n-)-maxDepth << endl;
return ;
}
思路：
1.給出k，區間長度固定
2.求出固定區間相同元素的數量大于t即可
3.用map存儲每個元素以及其數量，每個區間是個滑動視窗，每次區間向前移動一個位置，隻需要第一次周遊區間，對map初始化，随後區間每移動一次，隻需要改變新區間right值對應數量和上個區間left值對應數量即可
代碼：
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> MAP;
bool isFirst = true;
bool IsAccessT(vector<int>& arr, int left, int right, int t){
if(isFirst){//首個區間初始化
isFirst = false;
for(int i=left; i<=right; i++){
MAP[arr[i]]++;
}
}else{
MAP[arr[left-]]--;
MAP[arr[right]]++;
}
auto it = MAP.begin();
for(; it!=MAP.end(); it++)
if(it->second >= t)
return true;
return false;
}
int fun(vector<int>& arr, int k, int t){
int count = ;
for(int left=; left<arr.size(); ++left){
int right = k-+left;
if(right >= arr.size())
break;
if(right<arr.size() && IsAccessT(arr, left, right, t))
count++;
}
return count;
}
int main(){
int n,k,t;
cin >> n >> k >> t;
vector<int> arr;
for(int i=; i<n; i++){
int temp;
cin >> temp;
arr.push_back(temp);
}
int res = fun(arr, k, t);
cout << res << endl;
return ;
}