ARST打卡第305周

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

impl Solution {
    pub fn maximum_beauty(items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
        // 创建查询索引，以便后面还原顺序
        let n = queries.len();
        let mut indexed_queries: Vec<(i32, usize)> = queries.into_iter().enumerate().map(|(i, q)| (q, i)).collect();
        indexed_queries.sort_unstable(); // 按查询值排序
        
        // 按价格排序物品，价格相同时按美丽值降序排序
        let mut sorted_items = items;
        sorted_items.sort_unstable_by(|a, b| {
            if a[0] == b[0] {
                b[1].cmp(&a[1]) // 价格相同时，按美丽值降序
            } else {
                a[0].cmp(&b[0])
            }
        });
        
        // 预处理每个价格点的最大美丽值
        let m = sorted_items.len();
        let mut max_beauty = vec![0; m];
        max_beauty[0] = sorted_items[0][1];
        
        for i in 1..m {
            // 对于每个物品，最大美丽值是当前物品的美丽值或之前的最大美丽值
            max_beauty[i] = max_beauty[i-1].max(sorted_items[i][1]);
        }
        
        let mut result = vec![0; n];
        
        // 对于每个查询，二分查找不超过查询价格的最大索引
        for (query, original_idx) in indexed_queries {
            // 二分查找
            match sorted_items.binary_search_by(|item| {
                if item[0] == query {
                    std::cmp::Ordering::Equal
                } else {
                    item[0].cmp(&query)
                }
            }) {
                Ok(idx) => {
                    // 找到精确匹配，使用该位置的最大美丽值
                    result[original_idx] = max_beauty[idx];
                }
                Err(idx) => {
                    if idx > 0 {
                        // 使用小于查询价格的最大美丽值
                        result[original_idx] = max_beauty[idx - 1];
                    }
                }
            }
        }
        
        result
    }
}