美团劝退型笔试~

美团编程题（2018年9月6日）
第一题（提交之前没调出来，提交之后的5分钟内搞定了，应该是正确的吧~ 都怪前面的数学题和逻辑题占用了太多时间~）好气啊~ 美团劝退型笔试。

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <numeric>
using namespace std;

using vv = vector<vector<int>>;
int helper(vv& g, vector<bool>& visited, int pos, int n){
    int res(0);
    visited[pos] = true;
    vector<int> s;
    for (auto& v : g[pos]){
        if (!visited[v]){
            s.push_back(helper(g, visited, v, n) + 1);
            visited[v] = true;
        }
    }
    if (s.size() == 0) return 0;
    sort(s.begin(), s.end());
    for (int i = 0; i < s.size() - 1; i++){
        res += 2 * s[i];
    }
    res += s.back();
    return res;
}
int main(){
    int n;
    cin >> n;
    vv g(n + 1);
    int u, v;
    for (int i = 0; i < n - 1; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<bool> visited(n + 1, false);
    int res = helper(g, visited, 1, n);
    cout << res << endl;
}

第二题比较简单（AC）。

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <numeric>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> dp{ 0 };
    int num;
    for (int i = 1; i <= n; i++){
        cin >> num;
        if (num == 0) dp.push_back(i);
    }
    dp.push_back(n + 1);
    if (k >= dp.size() - 1){
        cout << n << endl;
        return 0;
    }
    int res(0);
    for (int i = k + 1; i < dp.size(); i++){
        res = max(res, dp[i] - dp[i - k - 1] - 1);
    }
    cout<<res<<endl;
    return 0;
}