简述题意

给定一个 $n$ 个元素的环形数组 $a$，$q$ 次查询，每次给定一个 $k$，将数组划分为若干个连续段，使得每一段的和都不超过 $k$，最小化连续段个数。

• $2\le n\le 10^6,1\le q\le 50$
• 1 ≤ a i ≤ 1 0 9 , max ⁡ { a i } ≤ k ≤ 1 0 15 1 \le a_i \le 10^9,\max\{a_i\} \le k \le 10^{15} 1≤ai​≤109,max{ai​}≤k≤1015

思路

先破环成链，然后求前缀和 $pre$。
对于每一个 $i$，不妨先双指针求出 $nx{t}_i$，表示最大的满足 $pr{e}_{nx{t}_i}-pr{e}_{i-1}\le k$ 的点。
显然，如果我们已经知道了某个连续段的起点，那么贪心的往后跳到 $nx{t}_i+1$，答案是固定的。
然而，如果直接枚举 $n$ 个起点，时间复杂度接受不了，考虑优化。
我们可以发现，无论怎么划分，连续段长度都存在一个下限，那就是 min ⁡ { n x t i − i + 1 } \min\{nxt_i-i+1\} min{nxti​−i+1}，那么每次贪心的时间复杂度即为 O ( n min ⁡ { n x t i − i + 1 } ) O(\dfrac{n}{\min\{nxt_i-i+1\}}) O(min{nxti​−i+1}n​)。不妨令 $nx{t}_i-i+1$ 最小的这个点为 $x$。

考虑进一步优化：减少枚举起点的数量。

观察上面那个式子的分母，可以想到，无论怎么划分，一定有一个连续段的起点在 $[x,nx{t}_x+1]$，否则一定划分出来有一个连续段的和大于 $k$，这是显然的。所以枚举起点的复杂度为 $O(nx{t}_x-x+1)$。

单次查询的时间复杂度为 $O(n)$。

代码

很简单的一道 $2400$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 5;
int n , q , a[MAXN] , nxt[MAXN];
ll pre[MAXN] , k;
int Path(int now) {if (now > n) now -= n;int l = 0 , sum = 0;while(l < n) {l += nxt[now] - now + 1;sum ++;now = nxt[now] + 1;}return sum;
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr) , cout.tie(nullptr); cin >> n >> q;for (int i = 1 ; i <= n ; i ++) cin >> a[i] , a[i + n] = a[i];for (int i = 1 ; i <= 2 * n ; i ++) pre[i] = pre[i - 1] + a[i];while(q --) {cin >> k;int len = 1e9 , st;for (int i = 1 , j = 1 ; i <= 2 * n ; i ++) {while(j < 2 * n && pre[j + 1] - pre[i - 1] <= k) j ++;nxt[i] = j;if (nxt[i] - i + 1 < len && i <= n) st = i , len = nxt[i] - i + 1;}int ans = 1e9;for (int i = st ; i <= nxt[st] + 1 ; i ++) ans = min(ans , Path(i));cout << ans << '\n';}return 0;
}