codeforces -- 4B. Before an Exam

tag： greedy，constructive algorithms，*1200

题目描述

思路

简而言之，有个总的时间，有天数，有每天可以用的时间范围，求总的时间能不能在这几天用完，且每天用的时间必须在给定的范围内，如果能够分配完总时间，则输出YES，并输出每一天的时间，否则输出NO。

可以先让每一天都用掉最小时间，如果总时间不够每天的最小时间之和，说明总时间不够分配给每一天，如果能够让每一天都能用掉最小时间，则把剩余的总时间从第一天到最后一天依次补最大时间和最小时间的差距，如果补完之后总时间还有剩的说明时间分配不完，否则可以分配完。

代码

use std::io::stdin;

fn main() {
    
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    let t = line.split_whitespace().map(|f| f.parse::<i32>().unwrap()).collect::<Vec<_>>();
    let (d, mut sum_time) = (t[0], t[1]);

    // 存每天的最小学习时间和最大学习时间
    let mut f = vec![vec![0;2];d as usize];
    // 存答案
    let mut ans = vec![0;d as usize];

    for i in 0..d {
    
        line = String::new();
        stdin().read_line(&mut line).unwrap();
        let t = line.split_whitespace().map(|f| f.parse::<i32>().unwrap()).collect::<Vec<_>>();
        let (min_time,  max_time) = (t[0], t[1]);
        // 存储每一天的最大学习时间和最小学习时间
        f[i as usize][0] = min_time;
        f[i as usize][1] = max_time;
        ans[i as usize] = min_time;
        sum_time -= min_time;
        // 先保证每天能达到最小学习时间
        if sum_time < 0 {
    
            println!("NO");
            return ;
        }
    }

    // 保证每天都学习最小时间之后，从头填补每一天的差距，看能否把剩余的时间用完
    for i in 0..d {
    
        let diff = f[i as usize][1] - f[i as usize][0];
        if sum_time > diff {
    
            sum_time -= f[i as usize][1] - f[i as usize][0];
            ans[i as usize] = f[i as usize][1];
        } else {
    
            ans[i as usize] = f[i as usize][0] + sum_time;
            sum_time = 0;
            break;
        }
    }

    if sum_time <= 0 {
    
        println!("YES");
        for i in ans {
    
            print!("{} ", i);
        }
    } else {
    
        println!("NO");
    }

}

时间复杂度：O(n)
空间复杂度：O(n)