字节10.15笔试

//第一题
int p;
int dis(int p1, int p2) {
    return abs(p1 - p2) + abs(p2 - p);
}
int main() {
    int n;
    cin >> n >> p;
    vector<int>per(n), good(n);
    for (int i = 0; i < n; i++) {
        cin >> per[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> good[i];
    }
    sort(per.begin(), per.end());
    sort(good.begin(), good.end());
    int ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dis(per[i], good[i]);
    }
    cout << ret << endl;
    return 0;
}
//第二题
int main() {
    int n;
    cin >> n;
    int color, type, know;
    vector<vector<int>>v(n,vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> color;
        v[i][0] = color;
    }
    for (int i = 0; i < n; i++) {
        cin >> type;
        v[i][1] = type;
    }
    for (int i = 0; i < n; i++) {
        cin >> know;
        v[i][2] = know;
    }
    sort(v.begin(), v.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] > b[2];
        });
    set<pair<int, int>>dic;
    int ret = 0;
    for (int i = 0; i < n; i++) {
        auto p = make_pair(v[i][0], v[i][1]);
        if (dic.count(p)) {
            ret += v[i][2] / 2;
        }
        else {
            dic.insert(p);
            ret += v[i][2];
        }
    }
    return ret;
}
//第三题：n个西瓜，p为优质品的概率。每个人从左到右购买，求优质x标准最大为多少，保证每一个人买到优质品的概率均大于p。
double p;
bool isValid(vector<int>&nums, int t, int id) {
    int n = nums.size(),len = n;
    double pp = 0;
    int positive = n - id;
    for (int i = 0; i < n; i++) {
        if (nums[i] < t) {
            pp = positive * 1.0 / len--;
        }
        else if (nums[i] >= t) {
            pp = (positive-- )*1.0/ len--;
        }
        if (pp < p)return false;
    }
    return true;
}
int main() {
    int n;
    cin >> n >> p;
    vector<int>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int>nums = a;
    sort(a.begin(),a.end());
    int ret = 0;
    //遍历a
    for (int i = 0; i < n; i++) {
        if (isValid(nums, a[i], i)) {
            ret = a[i];
        }
        else {
            break;
        }
    }
    cout << ret << endl;
    return 0;
}

//第四题:小红拿到了一个正方形矩阵，她准备从左上角走到右下角，小红每走一步可以向右或向下走一步。她想知道，有多少不同路径满足路径和的元素恰好等于x？
//dfs+回溯
int n, x, ret = 0;
vector<vector<bool>>visited;
void dfs(vector<vector<int>>& a, int i, int j, int sum) {
    if (i >= n || j >= n || visited[i][j] == true)return;
    visited[i][j] = true;
    sum += a[i][j];
    if (i == n - 1 && j == n - 1 && sum == x) {
        ret++;//不return回溯，return后面就走不到visited[i][j] = false;这个格子仍被标记为true；
    }
    dfs(a, i, j + 1, sum);
    dfs(a, i + 1, j, sum);
    visited[i][j] = false;
}
int main() {
    cin >> n >> x;
    vector<vector<int>>a(n, vector<int>(n));
    visited = vector<vector<bool>>(n, vector<bool>(n, false));//先初始化visited
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    dfs(a, 0, 0, 0);
    cout << ret << endl;
    return 0;
}