⭐AtCoder Beginner Contest 334

前言:
比赛题目链接
--按照惯例只写了主要部分的代码--
特别说明：Rust有一个竞赛用的输入库，并且写ABC是可以用的，但是平时写洛谷是用不了的，所以我自己写了一个cin(),凑活能用，代码见下：

读输入函数

fn cin() -> String {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    input.trim().to_string()
}

明明 2、3 都是简单题却过不了，果然是因为做了一天题导致晚上状态下滑了嘛

模拟只会猜题意，贪心只能过样例；数学上来先打表，DP一般看规律；组合数学靠运气，计算几何瞎暴力；图论强行套模板，数论只会GCD；递推莫名UKE，递归堆栈往外溢；深搜茫然TLE，广搜队列MLE；二分查找总CE，叉堆结果必RE；高精算法找规律，做完全都OLE；数据结构干瞪眼，水题也都WA;长知识也不容易，考试一来全懵Ｂ！

A

题目分析：

签到题，输出大的就行，题目还说明了不会有相等的情况

代码实现：

C++代码

void solve() {
    int b, g;
    cin >> b >> g;
    cout << (b > g ? "Bat" : "Glove");
}

Rust代码

fn solve() {
    let (a, b) = cin()
        .split_whitespace()
        .fold((0, 0), |x, y| (x.1, y.parse::<i32>().unwrap()));
    println!("{}", if a > b { "Bat" } else { "Glove" });
}

第二题

B

题目分析：

数学题，我们分别计算出 r 到 a 有多少点以及 l 到 a 有多少点。我们希望左区间减一后向下取整，右区间向下取整，接着作差得到答案

Rust代码中，我们使用div_euclid()实现向下取整。div_euclid() 是执行欧几里得除法，即找到\(Self=q*rhs+r\)中的 q ，实现向下取整（默认的除法是省略小数部分，并非向下取整）

代码实现：

C++代码

void solve() {
    long double a,m,l,r;
    cin >> a >> m >> l >> r;
    ll ans = floor((r - a) / m) - floor((l - 1 - a) / m);
    cout << ans;
}

Rust代码

fn solve() {
    let (a, b, c, d) = cin().split_whitespace().fold((0, 0, 0, 0), |x, y| {
        (x.1, x.2, x.3, y.parse::<i128>().unwrap()) //读输入
    });
    println!("{}", (d - a).div_euclid(b) - (c - 1 - a).div_euclid(b));
}

第三题

题目分析：
理解题意，题目中的袜子按递增顺序给出，而我们都知道差值最小的方案就是两个颜色最接近的，而对于任意两个袜子之间的最大值，我们按如下方式考虑：

不难想到，每次取相邻的得到的差是最小的

而得到的差即为n-1，而这等于直接将x_n与x₁配对

于是我们得到结论，每次取相邻两个之间的差即可
但对于奇数个的情况，我们需要找到哪个是需要不配对的，也就是找出最小值
可以先将第一个排除，我们得到后\(\lfloor \frac{n}{2}\rfloor\)对的和，即：

接着我们开始向后遍历，每次取前两个差的和减去后两个差的和：

这里我们假设蓝色会与绿色相消，那么得到的结果就是：

那么依次执行，每次比较这个值和一开始的值哪个小，遍历完之后得到结果
代码部分：

C++代码

void solve() {
    int n, i, ans = 0;
    cin >> n >> n;
    vector<int> qwq(n);
    for(auto &x : qwq)cin >> x;
    for(i = n % 2 == 0 ? 1 : 2;i < n;i += 2)ans += qwq[i] - qwq[i - 1];
    if(n % 2 == 1) {
        int now = ans;
        for(i = 1;i < n;i += 2) {
            now += 2 * qwq[i] - qwq[i - 1] - qwq[i + 1];
            ans = min(ans, now);
        }
    }
    cout << ans;
}

Rust代码

fn solve() {
    let (_, n) = cin()
        .split_whitespace()
        .fold((0, 0), |x, y| (x.1, y.parse::<usize>().unwrap()));
    let qwq = cin()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect::<Vec<i32>>();
    let st = if n % 2 == 1 { 2 } else { 1 };
    let mut ans = 0;
    for i in (st..n).step_by(2) {
        ans += qwq[i] - qwq[i - 1];
    }
    if st == 2 {
        let mut now = ans;
        (1..n - 1).step_by(2).for_each(|i| {
            now += 2 * qwq[i] - qwq[i - 1] - qwq[i + 1];
            ans = ans.min(now);
        })
    }
    println!("{}", ans);
}

第四题

D

题目分析：
我们知道最小的两个货物数之和肯定是最小的，我们每次取最小的肯定是最理想的情况
于是我们先对数组排个序，接着求出前缀和数组，得到的数组的索引加一就是能拉的货物数量，只需判断给定的鹿的数量在数组中的哪个位置即可，所以我们利用二分查找得到答案。
记得开long long

十年OI一场空，不开long long见祖宗

代码部分：

C++代码

void solve() {
    int n, q, i;
    ll j;
    cin >> n >> q;
    vector<ll>qwq(n);
    for(auto &x : qwq)cin >> x;
    sort(qwq.begin(), qwq.end());
    for(i = 1;i < n;++i)qwq[i] += qwq[i - 1];
    for(i = 0;i < q;++i) {
        cin >> j;
        cout <<' '<< (upper_bound(qwq.begin(), qwq.end(), j)-qwq.begin())<<'\n';
    }

}

Rust代码

fn solve() {
    let (a, b) = cin()
        .split_whitespace()
        .fold((0, 0), |x, y| (x.1, y.parse::<usize>().unwrap()));
    let mut qwq = cin()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect::<Vec<i128>>();
    qwq.sort_unstable();
    (1..a).for_each(|x| qwq[x] += qwq[x - 1]);
    for _ in 0..b {
        let n: i128 = cin().parse().unwrap();
        println!("{}", qwq.partition_point(|&x| x <= n))
    }
}