题解

刚抄完历史作业。

首先注意到题目要求最短空题段，所以我们可以联想到经典题目：数列分段。数列分段这道题是使用二分加贪心解决的。

定义 $f(x)$ 为每个空题段不超过 $x$ 时最少所需的时间。注意到 $f(x)$ 是满足单调性的，所以可以二分答案。

现在的问题是如何快速求出 $f(x)$。

贪心显然不行，考虑 DP。

定义 $\text{dp}_i$ 为做到第 $i$ 个题最少所花时间。则有：

$$\text{dp}_i=\min_{j={i-x}}^{i-1} \text{dp}_j+A_i$$

然后就是 $f(x)=\min_{j=n-x+1}^n \text{dp}_j$。

暴力是 $O(n^2\log n)$ 的，但显然可以通过线段树优化到 $O(n\log^2 n)$。

以下是代码实现。

实现与思路有所差异，例如我的线段树是 1-based 的，所以每个下标都加了 $1$；还有我偷了点懒，直接将 $A_i(i\gt n)=0$，然后求出 $\text{dp}_{2n}$。

#include <iostream>
#include <cstdio>
#include <vector>
namespace cjdst{

	template <typename T>
	class Fenwick_Tree{
		std::vector <T> tr;
		int n;

		public:

		Fenwick_Tree(){}
		Fenwick_Tree(int n, std::vector <T> a){
			tr.resize(n + 5, 0);
			this -> n = n;
			for(int i = 1; i <= n; i++){
				tr[i] += a[i];
				if(i + (i & (-i)) <= n){
					tr[i + (i & (-i))] += tr[i];
				}
			}
		}
		void modify(int idx, T val){
			for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
		}
		T query(int idx){
			T ans = 0;
			for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
			return ans;
		}
	};

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		void push_up(int u){
			tr[u] = std::min(tr[u << 1], tr[u << 1 | 1]);
		}
		void build(int u, int l, int r){
			left[u] = l, right[u] = r;
			if(l == r){
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
			push_up(u);
		}
		void _modify(int u, int idx, T val){
			if(left[u] == right[u]){
				tr[u] = val;
				return;
			}
			if(right[u << 1] >= idx) _modify(u << 1, idx, val);
			if(left[u << 1 | 1] <= idx) _modify(u << 1 | 1, idx, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			T ans = 0x3f3f3f3f3f3f3f3fll;
			if(right[u << 1] >= l) ans = std::min(ans, _query(u << 1, l, r));
			if(left[u << 1 | 1] <= r) ans = std::min(ans, _query(u << 1 | 1, l, r));
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n){
			tr.resize(n * 4 + 5, 0x3f3f3f3f3f3f3f3fll);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			build(1, 1, n);
		}
		void modify(int idx, T val){
			_modify(1, idx, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;
	
	std::vector <ll> a;
	int n, m;
	bool check(int val){
		Segtree <ll> dp(n * 2 + 5);
		dp.modify(1, 0);
		for(int i = 1; i <= n * 2; i++){
			ll cur = dp.query(std::max(1, i - val), std::max(1, i)) + a[i];
			dp.modify(i + 1, cur);
		}
		return (dp.query(n + 1, n * 2 + 1) <= m ? 1 : 0);
	}
	void solve(){
		std::cin >> n >> m;
		a.resize(n * 2 + 5, 0);
		for(int i = 1; i <= n; i++) std::cin >> a[i];
		int l = 1, r = n;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(check(mid)) r = mid - 1;
			else l = mid + 1;
		}
		std::cout << l << '\n';
	}
}


int main(){
	int T = 1;
	cjdst::init();
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

时间复杂度：$O(n\log^2 n)$。