Codeforces 363B: Fence & Rust for Competitive Programming

Codeforces 363B C++/Rust 一解, 以及 Rust 在竞赛中的一些事项.

分析

这道题本身比较简单, 所谓的动态规划就是前缀和: 跑完一遍前缀和之后遍历一遍找出最小值即可. 本文主要是记录 Rust 写竞赛题时需要注意的和 C++ 不太一样的地方. 当然相对而言 C++ 常常能写出短小的代码, 但是 Rust 更能在编译时跟踪许多错漏, 以至于目前的所有 Rust 提交都是一遍 AC.

一些需要注意的地方:

• Rust 默认的变量都是不可变的, 记得添加 mut 关键字;
• Rust 的索引必须为 usize 类型, 不能随便乱用 i32 或 i64;
• Rust 开固定大小数组的方式: Vec::with_capacity(n), 注意 n 也为 usize 类型;
• Rust 虽然要关注所有权的问题, 但是一般的代码还是不需要用到 &;
• Rust 很多函数和方法用到了 Result, Some, Option 等特殊类型作为返回类型, 需要注意如何处理这些数据 (例如 .unwrap(), .ok()).

代码

#include <bits/stdc++.h>

using namespace std;

int h[150001], s[150001];

int main() {
    int n, k, minsum = 0x7fffffff, minsumpos;

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        s[i] = s[i - 1] + h[i];
    }

    for (int i = 1; i <= n - k + 1; ++i) {
        if (s[i + k - 1] - s[i - 1] < minsum) {
            minsum = s[i + k - 1] - s[i - 1];
            minsumpos = i;
        }
    }

    cout << minsumpos << endl;

    return 0;
}

Rust 部分最重要的代码部分位于 // Write code here 以下, 其他的部分是读入数据的模板, 不必过多在意.

#[allow(unused_imports)]
use std::io::{BufWriter, stdin, stdout, Write};

#[derive(Default)]
struct Scanner {
    buffer: Vec<String>
}
impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn main() {
    let mut scan = Scanner::default();
    let out = &mut BufWriter::new(stdout());

    // Write code here
    let n: usize = scan.next();
    let k: usize = scan.next();
    let mut hs: Vec<i32> = Vec::with_capacity(n);
    for _ in 0..n {
        let h: i32 = scan.next();
        hs.push(h);
    }
    let mut hhs: Vec<i32> = Vec::with_capacity(n + 1);
    hhs.push(0);
    for i in 0..n {
        hhs.push(&hs[i] + &hhs[i]);
    }
    let mut m = 0x7fffffff;
    let mut mpos = 0;
    for i in k..=n {
        if hhs[i] - hhs[i - k] < m {
            m = hhs[i] - hhs[i - k];
            mpos = i - k + 1;
        }
    }
    writeln!(out, "{}", mpos).ok();
}