H_On个人小站

个人站

这都被你发现了【惊
奖励你一朵小红花~


【Codeforces Round#621 (Div. 1 + Div. 2)】A. Cow and Haybales 题解

题目链接:A. Cow and Haybales

题目

一直觉得英文题题面很难理解,然后也有题目链接,很纠结要不要每次都把题目再写一遍,昨天看大佬题解是贴一个截图上去,感觉也不错,以后我就这么干辣

A 题题面

题意

有 n 个按顺序放好的草堆,k 次搬运机会,每次只能从一个草堆搬运一个单位的草到相邻的另一个草堆,问你搬运完之后第一堆草堆的草最多会是多少。

解题思路

这个题有几个解体的点:

  1. 草堆是按顺序摆放的,求 第一堆 最大是多少
  2. 草只能在 相邻 的草堆中搬运
  3. 一次只能搬运一个单位的草

那么大家思考一下,我们只要尽量把后面的草搬到第一堆即可

  • 第二堆的草搬到第一堆只要搬一次
  • 第三堆的草搬到第一堆要搬两次
  • 第四堆的草搬到第一堆要搬三次
  • . . .

所以我们只要从第二堆开始遍历,尽量往第一堆搬草就可以了

代码

注释:

  1. 由于是要边输入边操作,因此使用一个 flag ,当搬运机会已经用完的时候跳过操作代码
  2. 循环中的 k 是 剩余搬运次数 ,i 是 将当前堆的一单位草搬到第一堆需要的搬运次数
  3. 由于 0 不能当除数,因此特判跳过对第一组的操作
  4. k/i 即为:剩余次数能将这个堆多少草搬运到第一堆
    • 如果可搬运次数大于等于此堆草量,结果加上此堆所有的草,剩余次数减去搬运消耗的次数
    • 否则结果只加上 能够搬运的草 ,剩余次数减去搬运消耗的次数
  5. 不难发现,注释 4 中的判断实际上就是取总草量和可搬运草量的最小值,因此代码也可以优化成这样
  6. 最后如果 k 已经不能够完成一次搬运的话,就将可搬运标记 f 置为假。ps:亲测有一个很奇怪的事情:这里的判断 条件如果写 !k || k < i 提交时间是 15ms ,然而如果条件简单的写成 k < i 提交时间是 30ms ,大概是比较操作比判 0 操作需要时间更长
#include <iostream>
using namespace std;

int main() {
        ios::sync_with_stdio(0); cin.tie(0);
        int t; cin >> t;
        while (t--) {
                int n, k, r = 0; cin >> n >> k;
                //注释 1
                bool f = true;
                for (int i = 0; i < n; i++) {
                        int a; cin >> a;
                        //注释 3
                        if (!i) {r += a; continue;}
                        //如果还可以搬运,就尝试搬运一下
                        if (f) {
                                //注释 4,同时参考注释 2
                                int q = k/i;
                                if (q >= a) r += a, k -= i*a;
                                else r += q, k -= i*q;
                                /*
                                //注释 5
                                int q = min(k/i, a);
                                r += q, k -= i*q;
                                */
                                //注释 6
                                if (k < i) f = false;
                        }
                }
                cout << r << endl;
        }
        return 0;
}