小红书笔试20220828

第一题：用排序就行了

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    // 输出数据处理
    int n, m, id;
    cin >> n >> m >> id;
    vector<vector<int>> nums(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> nums[i][j];
        }
    }

    // 解题
    vector<pair<int, long long>> scores;
    for (int i = 0; i < nums.size(); ++i) {
        long long sum = 0;
        for (int j = 0; j < nums[i].size(); ++j) {
            sum += nums[i][j];
        }
        scores.push_back({i+1, sum});
    }
    // sort
    sort(scores.begin(), scores.end(),
         [](const pair<int, long long> &lhs, const pair<int, long long> &rhs) {
             if (lhs.second == rhs.second)
                 return lhs.first < rhs.first;
             else
                 return lhs.second > rhs.second;
         });
    // print
    for(int i = 0; i < scores.size(); ++i){
        if(scores[i].first == id){
            cout << i+1 << endl;
            break;
        }
    }
    return 0;
}

第二题：双重循环暴力会超时，可以先排序，然后二分查找，把时间复杂度降到O(nlogn)

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    // 输入数据处理
    double n, k;
    cin >> n >> k;
    vector<double> nums(n, 0);
    for(int i = 0; i < n; ++i){
        cin >> nums[i];
    }
    // solve
    long long ans = 0;
    // sort
    sort(nums.begin(), nums.end());
    for(auto iter = nums.begin(); iter != nums.end(); ++iter){
        auto pos = lower_bound(iter+1, nums.end(), k / (*iter));
        ans += nums.end()-pos;
    }
    cout << ans*2 << endl;
    return 0;
}

第三题：图的遍历。每一次遍历要取相邻两个点组成一对好友，然后再递归到下一个点

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

vector<bool> vis;
unordered_map<int, vector<int>> myMap;
int ans = INT32_MIN;
void dfs(int idx, int cnt){
    vis[idx] = true;
    for(int n : myMap[idx]){
        if(!vis[n]){
            vis[n] = true;
            cnt++;
            ans = max(ans, cnt);
            for(int nn : myMap[n]){
                if(!vis[nn]) dfs(nn, cnt);
            }
            cnt--;
            vis[n] = false;
        }
    }
    vis[idx] = false;
}
int main(){

    // 输入数据处理
    int n;
    cin >> n;
    vector<int> nums(n-1, 0);
    for(int i = 0; i < n-1; ++i){
        cin >> nums[i];
    }

    // solve
    // map表的构造
    vis.resize(n+1, false); // 1-n
    for(int i = 0; i < nums.size(); ++i){
        myMap[i+2].push_back(nums[i]);
        myMap[nums[i]].push_back(i+2);
    }
    for(int i = 1; i <= n; ++i){
        dfs(i, 0);
    }
    cout << ans << endl;
    return 0;
}