$n$ 个糖果店,围成一圈。
店铺按顺时针顺序从 $1$ 到 $n$ 编号,$n$ 号店铺与 $1$ 号店铺相邻。
第 $i$ 号店铺的单个糖果售价为 $a_i$ 元。
李华拿着 $T$ 元钱去购买糖果,具体购买过程如下:
- 初始时,他位于 $1$ 号店铺。
- 如果他现有的钱足够在当前店铺购买一个糖果,他就会立即购买一个糖果,否则他将不会在当前店铺购买糖果。随后,不论他是否在当前店铺购买糖果,他都会按顺时针顺序前往下一个店铺。
- 他将不断重复过程 $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$。
输入样例1:
3 38
5 2 5
输出样例1:
10
输入样例2:
5 21
2 4 100 2 6
输出样例2:
6
思路
这题看着花里胡哨,实则解法非常暴力,我们只用一轮一轮的模拟即可,用cnt记录可以买到的糖果数。
- 初始先计算如果所有的糖果都买需要多少钱,记为$sum$。
- 如果我们的钱$t$大于$sum$,那我们就可以通过:当前店铺数$\times t\div sum$来得到我们可以一直买下去的糖果数,之后我们的金钱变为$t%sum$。
- 当$sum$大于$t$时,我们遍历一遍所有的店铺,如果这个店铺的糖果我们能买,则$cnt++$,金钱减去这个店铺的售价$a[i]$。如果这个店铺的糖果我们不能买,我们用$st$数组记录下这个店铺,并把它从$sum$中减去。
- 重复第$2,3$操作,知道我们一个糖果都买不了为止。
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
LL t;
LL a[N];
bool st[N];
int main () {
cin >> n >> t;
LL sum = 0,minv = 2e9;
for (int i = 1;i <= n;i++) {
cin >> a[i];
sum += a[i];
}
LL ans = 0,cnt = n;
while (1) {
bool flag = false;
ans += t / sum * cnt;
t %= sum;
for (int i = 1;i <= n;i++) {
if (st[i]) continue;
if (t >= a[i]) {
t -= a[i];
ans++;
flag = true;
}
else {
st[i] = true;
sum -= a[i];
cnt--;
}
}
if (!flag) break;
}
cout << ans << endl;
return 0;
}
直到写成知道了