1、给定一个整数序列，求中位数。

https://www.nowcoder.com/questionTerminal/2364ff2463984f09904170cf6f67f69a

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

int main(){
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    sort(nums.begin(), nums.end());
    if (n % 2) cout << nums[n / 2] << endl;
    else cout << (nums[n / 2 - 1] + nums[n / 2]) / 2.0 << endl;
}

2、ISBN 校验位

#include <iostream>

using namespace std;

int main() {
    string str;
    cin >> str;
    int k = 10, s = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] >= '0' && str[i] <= '9') {
            s += (str[i] - '0') * k;
            k--;
        }
    }
    int m = s % 11;
    int M = 11 - m;
    if (M >= 1 && M <= 9) {
        str += '-';
        str += ('0' + M);
    }
    else if (M == 10) {
        str += "-X";
    }
    else if (M == 11) {
        str += "-0";
    }
    cout << str;
    return 0;
}

3、Kruskal 算法

https://www.nowcoder.com/practice/16212f7d46e44174b5505997ea998538?tpId=40&tqId=21449&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking&tab=answerKey

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>

using namespace std;

struct Road{
    int x, y, cost;
    Road(int x, int y, int cost) : x(x), y(y), cost(cost){}
    bool operator < (const Road& r) const {
        return cost < r.cost;
    }
};
class UF{
public:
    vector<int> fa;
    int comp_cnt;
public:
    UF(int n) : fa(n), comp_cnt(n){
        iota(fa.begin(), fa.end(), 0);
    }
    int findFa(int x){
        return x == fa[x] ? x : fa[x] = findFa(fa[x]);
    }
    void unite(int x, int y){
        x = findFa(x), y = findFa(y);
        if(x != y) fa[y] = x;
    }
    bool isConnected(int x, int y){
        return findFa(x) == findFa(y);
    }
};
int main(){
    int N;
    while(cin >> N && N){
        UF uf(N);
        vector<Road> roads;
        int city1, city2, cost, state;
        for(int i = 0; i < N*(N - 1)/2; i ++){
            cin >> city1 >> city2 >> cost >> state;
            if(state == 1) uf.unite(city1 - 1, city2 - 1);
            else roads.emplace_back(city1 - 1, city2 - 1, cost);
        }
        sort(roads.begin(), roads.end());
        int minCost = 0;
        for(Road road : roads){
            if(!uf.isConnected(road.x, road.y)){
                uf.unite(road.x, road.y);
                minCost += road.cost;
            }
        }
        cout << minCost << endl;
    }
    return 0;
}