金币_牛客博客

算法思路关键洞察这个问题的核心在于识别金币发放的模式：发放阶段：金币数相同的连续天数构成一个阶段阶段长度：第 k 个阶段包含 k 天，每天发放 k 枚金币累计天数：前 m 个阶段的总天数为三角形数：1 + 2 + 3 + ... + m = m(m+1)/2 解决方案步骤确定完整阶段：找出包含第 N 天的完整发放阶段分类计算：完整阶段的金币总数（使用平方和公式）最后一个不完整阶段的金币数（如有）代码实现 use std::io; fn main() { //println!("Please enter the number of days:"); let mut input = String::new(); io::stdin().read_line(&mut input).expect("Failed to read line"); let input_day = input.trim().parse::().expect("Please input a type of u32 number"); let (number_of_gold_coin_a_day,sum_days_of_different_glod_coin) = get_number_of_glod_coin_a_day(&input_day); //println!("The number of gold coin a day is {} and the sum day is {}",number_of_gold_coin_a_day,sum_days_of_different_glod_coin); let sum_number_of_same_gold_coin = number_of_gold_coin_a_day * (input_day - sum_days_of_different_glod_coin); let n = number_of_gold_coin_a_day - 1; let sum_number_of_different_gold_coin = n*(n+1)(2n+1)/6; //println!("sum_number_of_same_gold_coin is {}",sum_number_of_same_gold_coin); //println!("sum_number_of_different_gold_coin is {}",sum_number_of_different_gold_coin); let result = sum_number_of_same_gold_coin + sum_number_of_different_gold_coin; print!("{}",result); }

fn get_number_of_glod_coin_a_day(day:&u32)->(u32,u32){ let max_day = 10000; let mut sum_day = 0; let mut old_sum_day = 0; let mut n=1; while sum_day <= max_day { sum_day = n*(n+1)/2; if sum_day == *day{ return (n,old_sum_day); } else if sum_day > *day{ return (n,old_sum_day); } n += 1; old_sum_day = sum_day; }; return (n,old_sum_day); }

#[test] fn test_get_number_of_glod_coin_a_day(){ assert_eq!(get_number_of_glod_coin_a_day(&1),(1,0)); assert_eq!(get_number_of_glod_coin_a_day(&2),(2,1)); assert_eq!(get_number_of_glod_coin_a_day(&3),(2,1)); assert_eq!(get_number_of_glod_coin_a_day(&4),(3,3)); assert_eq!(get_number_of_glod_coin_a_day(&5),(3,3)); }