简述题意
给定一个 n n n 个元素的环形数组 a a a, q q q 次查询,每次给定一个 k k k,将数组划分为若干个连续段,使得每一段的和都不超过 k k k,最小化连续段个数。
- 2 ≤ n ≤ 1 0 6 , 1 ≤ q ≤ 50 2 \le n \le 10^6, 1 \le q \le 50 2≤n≤106,1≤q≤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
思路
先破环成链,然后求前缀和 p r e pre pre。
对于每一个 i i i,不妨先双指针求出 n x t i nxt_i nxti,表示最大的满足 p r e n x t i − p r e i − 1 ≤ k pre_{nxt_i} - pre_{i-1} \le k prenxti−prei−1≤k 的点。
显然,如果我们已经知道了某个连续段的起点,那么贪心的往后跳到 n x t i + 1 nxt_i+1 nxti+1,答案是固定的。
然而,如果直接枚举 n n 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)。不妨令 n x t i − i + 1 nxt_i-i+1 nxti−i+1 最小的这个点为 x x x。
考虑进一步优化:减少枚举起点的数量。
观察上面那个式子的分母,可以想到,无论怎么划分,一定有一个连续段的起点在 [ x , n x t x + 1 ] [x,nxt_x+1] [x,nxtx+1],否则一定划分出来有一个连续段的和大于 k k k,这是显然的。所以枚举起点的复杂度为 O ( n x t x − x + 1 ) O(nxt_x-x+1) O(nxtx−x+1)。
单次查询的时间复杂度为 O ( n ) O(n) O(n)。
代码
很简单的一道 2400 2400 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;
}