rust_basic_code/md_file/1626. 无矛盾的最佳球队.md

1626. 无矛盾的最佳球队

description：

​ 假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

代码：

use std::cmp;

fn main() {
    let a = vec![1, 2, 3, 5];
    let b = vec![8, 9, 10, 1];
    let res = best_team_score(&a, &b);
    println!("res is: {}", res);
    
    let mut vec = Vec::with_capacity(5);  // 每次满了后 capacity *= 2
// The vector contains no items, even though it has capacity for more
    println!("vec.len() is: {}, vec.capacity() is: {}", vec.len(), vec.capacity());
// These are all done without reallocating...
    for i in 0..10 {
        vec.push(i);
        println!("vec.len() is: {}, vec.capacity() is: {}", vec.len(), vec.capacity());
    }
    println!("vec.len() is: {}, vec.capacity() is: {}", vec.len(), vec.capacity());
// ...but this may make the vector reallocate
    vec.push(11);
    println!("vec.len() is: {}, vec.capacity() is: {}", vec.len(), vec.capacity());
// A vector of a zero-sized type will always over-allocate, since no
// allocation is necessary
    let vec_units = Vec::<()>::with_capacity(10);
    println!("vec.len() is: {}, vec.capacity() is: {}", vec_units.len(), vec_units.capacity());
}

fn best_team_score(scores: &[i32], ages: &[i32]) -> i32{
    let n = scores.len();
    let mut people: Vec<(i32, i32)> = Vec::with_capacity(n);
    for i in 0..n {
        people.push((scores[i], ages[i]));
    }
    people.sort();
    let mut dp: Vec<i32> = vec![0; n];
    let mut res = 0;
    for i in 0..n {
        for j in (0..i).rev() {
            if people[j].1 <= people[i].1 {
                dp[i] = cmp::max(dp[i], dp[j]);
                // dp[i] = dp[i].max(dp[j]);
            }
        }
        dp[i] += people[i].0;
        res = cmp::max(res, dp[i]);
    }
    res
}

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<pair<int, int>> people;
        for (int i = 0; i < n; ++i) {
            people.push_back({scores[i], ages[i]});
        }
        sort(people.begin(), people.end());
        vector<int> dp(n, 0);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (people[j].second <= people[i].second) {
                    dp[i] = max(dp[i], dp[j]);
                }
            }
            dp[i] += people[i].first;
            res = max(res, dp[i]);
        }
        return res;
    }
};