去 AtCoder 打比赛了，错过了这次周赛TAT

这次周赛题目好像比较水？

4623.买糖果

$n$ 个糖果店，围成一圈。

店铺按顺时针顺序从 $1$ 到 $n$ 编号，$n$ 号店铺与 $1$ 号店铺相邻。

第 $i$ 号店铺的单个糖果售价为 $a_i$ 元。

李华拿着 $T$ 元钱去购买糖果，具体购买过程如下：

1. 初始时，他位于 $1$ 号店铺。
2. 如果他现有的钱足够在当前店铺购买一个糖果，他就会立即购买一个糖果，否则他将不会在当前店铺购买糖果。随后，不论他是否在当前店铺购买糖果，他都会按顺时针顺序前往下一个店铺。
3. 他将不断重复过程 $2$，直到剩余的钱在所有店铺都买不起糖果为止。

请问，最终李华一共购买到多少个糖果。

输入格式

第一行包含两个整数 $n,T$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一个整数，表示一共购买到的糖果数量。

数据范围

前 $6$ 个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n \le 2 \times 10^5$，$1 \le T \le 10^{18}$，$1 \le a_i \le 10^9$

解题思路

观察题意，显然可以直接暴力解决。

具体来说，可以将答案为两部分的和分别暴力解决：

我们不妨假设李华每走完一圈后 最多 花费 $sum$ 元，走了 $X$ 圈后剩下 $Y$ 元钱 $(0 \le Y \le sum)$

• 答案的其中一部分为李华走 $X$ 圈后的总收益，也就是获得收益 $X \times n$ 个糖果

• 另一部分为李华用剩下 $Y$ 元钱后获得的总收益

剩下 $Y$ 元钱后获得的总收益分为几步解决：

1. 计算李华目前能再走几圈

2. 更新答案，也就是加上 当前店铺数 $\times$ 当前钱数 $\times sum$

3. 动态更新 $sum$。如果遇到没有钱买糖果的商店，如果标记过就直接跳过没有就标记。如果有钱买这家商店的糖果，$ans$ 加上 $1$

4. 回到第一步

其他内容详见代码

c++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200009;

ll n, T, a[N];//不开 long long 见祖宗
ll cnt, sum = 0, ans = 0;
bool v[N], flag;

int main()
{
    cin >> n >> T;//输入店铺数和钱数
    for (ll i = 1; i <= n; ++ i)
    {
        v[i] = false;
        cin >> a[i];//输入第 i 号店铺的单个糖果售价
        sum += a[i];
    }

    cnt = n;

    while (1)//参考了 “你好A” dalao 更加简便的写法
    {
        ans += cnt * (T / sum);//更新答案
        T %= sum; flag = false;
        for (int i = 1; i <= n; ++ i)
        {
            if (v[i]) continue;
            if (T >= a[i])
            {
                flag = true;
                ans ++;
                T -= a[i];
            }
            else
            {
                v[i] = true;
                sum -= a[i];
                cnt --;
            }
        }
        if (!flag) break;//如果没有能买糖果的商店，直接跳出循环
    }

    cout << ans << endl;

    return 0;
}