acw - 4623. 买糖果（思维，取模折半）

https://www.acwing.com/problem/content/4626/

题意
n 个糖果店，围成一圈，按顺时针顺序从 1 到 n 编号，n 号店铺与 1 号店铺相邻。

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

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

初始时，他位于 1 号店铺。

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

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

$1\le n\le 2\times 10^5，1\le T\le 10^{18}，1\le a_i\le 10^9$

思路
一开始的是这样想的，如果有一轮走到某个位置发现这个位置拿不了，那么后面所有轮这个位置都拿不了，那么这个位置就可以删掉。T 很大，每次肯定要除以每轮的花费，看能进行多少次这样的轮，如果这一轮进行不了了，那么就删掉拿不了的那些位置，把剩下的花费加起来，再看能跑多少轮。。然后就想，这样最坏情况下每次遍历删掉一个位置，而一共 2e5 个位置，岂不是要遍历 2e5 次？2e5 * 2e5 就爆掉了。然后就没有思路了。。

其实，并不需要遍历 2e5 次。
没有考虑到 T 的变化。
每遍历一次，对于没删掉的位置作为一轮，看能够进行了多少轮，然后 T 减去这些轮的花费。其实这个就是 T 模上 sum，模过之后 T 至少是减半的！ 最多减半 log1e18 = 60 次就变成 0，不需要遍历了。

证明：
如果 sum < T/2，T % sum < T/2；
如果 sum ≥ T/2，T % sum = T - sum ≤ T/2。
所以，T % sum 之后，至少变为原来的 1/2。

那么这题的复杂度就为 O(nlogT)，60n。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	int ans = 0;
	while(1)
	{
		int sum = 0, cnt = 0;
		for(int i=1;i<=n;i++)
		{
			if(a[i] <= m){
				m -= a[i];
				sum += a[i];
				cnt ++;
			}
		}
		if(!cnt) break;
		ans += cnt;
		ans += m / sum * cnt;
		m %= sum; //m每次取模，导致折半减少 
	}
	cout << ans << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36