[100 challenge Array/List] P1214 Haybale Feast | ★ Solution

~~真丢脸这么简单的题目提交了五次~~
一看到farmer John就知道这题肯定是出自USACO了。果不其然，出自USACO 2017的一道G题。

题意

有若干个草堆线性排列，每个草堆都有风味F和辣值S两个参数。定义一道菜为连续的一个或若干个草堆，菜的风味值为所有风味的总和，辣值为所有草堆中最大的辣值。求在风味值超出给定的阈值的前提下最小的辣味值。
注意到F和M的取值，三年oi一场空，不开longlong见祖宗。

思路

朴素的尺取法

尺取法又称双指针（2ptr），是两个指针滑动产生的算法，时间复杂度为O(n)。而它最大的优点在于可以快速抛弃后面的，加入前面的，这也是它的要求。因此对于原题中的数组顺序不可改变的、有大量区间异或值、求和、求积的题目，2ptr很有优势。这题涉及到了F求和，因此不妨一试。

import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String[] tmp = sc.nextLine().split(" ");
		if(tmp[0].isEmpty()) tmp = sc.nextLine().split(" ");
		int n; long m;
		n = Integer.parseInt(tmp[0]); m = Long.parseLong(tmp[1]);
		long[] F = new long[n], S = new long[n];
		for(int i = 0; i < n; i++)
		{
			tmp = sc.nextLine().split(" ");
			if(tmp[0].isEmpty()) tmp = sc.nextLine().split(" ");
			F[i] = Long.parseLong(tmp[0]); S[i] = Long.parseLong(tmp[1]);
		}
        // input over
		int p, q;
		p = q = 0;
		long sum = F[0], g_min = S[0];
		while(p < n)
		{
			if(sum < m)
			{
				if(p < n-1) sum += F[++p];
				else break;
			}
			else
			{
				long max = S[p];
				for(int i = q; i <= p; i++)
					if(S[i] > max)
						max = S[i];
				if(max < g_min) g_min = max;
				if(q < p) sum -= F[q++];
				else break;
			}
		}
		System.out.println(g_min);
	}
}

显然这段代码并不work。虽然在求和方面很有优势，但求最大值最小值方面很不擅长，复杂度是直接O(n)了，那总的复杂度就变成了O(n^2)，是不能满足1e6的数据量的。

二分法

这题确实不容易想到二分，但单从复杂度上看似乎也能看出一些端倪。二分的复杂度是O(log)级别的，1e6的log也就20左右，再配合一个求min/max总的也只有O(nlogn)，看起来是完全胜任的。
二分答案的前提是答案是有序的。举例来说，如果答案为10时可以，那么比10小的就一定可以，比10大的就一定不可以。注意这里的充要性。
仔细想想这道题，答案一定在有限的、给定的S中取，而且是求最小值的，这也就意味着有很大可能性是可以二分的。于是我们写出二分的代码

int l = 0, r = n-1, mid;
while(l < r)
{
    mid = (l+r) >> 1;
    if(check(mid)) // mid 是一个可行解，往小里找
        r = mid; // 注意到mid是可行解，因此保边界。注意这里的改动导致while的条件发生变化以防止死循环
    else
        l = mid + 1;
}

对于check函数，我们只需要从mid出发，找出两边不超过当前S的部分，只要加起来大于m，就找到了一组最优情况，返回true，如果最后还是没有找到，返回false

bool check(int mid)
{
	int idx = hay[mid].idx;
	long sum = hay[mid].F;
	int p = idx+1;
	while(p < n && S[p] < hay[mid].S)
	{
		sum += F[p++];
		if(sum >= m)
			return true;
	}
	p = idx-1;
	while(p >= 0 && S[p] < hay[mid].S)
	{
		sum += F[p--];
		if(sum >= m)
			return true;
	}
	return false;
}

交了之后你会发现只有50分。我们不妨再思考一下，这样真的具有单调性吗？举个例子

显然，正确答案是9，而且单独一个 10 9 就可以满足题意了。但是，我们会直接枚举到10，竟然发现是不合法的！因为只有4+6才具备效力，根本无法预见到还有F更大S更小的情况。
那应该怎么办呢？调整check就可以了。check表达为“S不超过二分出来的最大值时能找到的最优方案。”代码如下

bool check(long max)
{
    long sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(S[i] <= max) sum += F[i];
        else sum = 0;
        if(sum >= m) return true;
    }
    return false;
}

从而这题就解决了。

再探尺取法

尺取法真的不可吗？其实未必。尺取法本身的复杂度是O(n)，是求min/max让他的复杂度再乘了一个n，那只需要把后面的那个n降到log n这题就能解决了。那查询最值有什么logn的办法吗？有。st表、QMR。因此很多人拿此题当st表的练手题，这也是评级是绿题的原因。由于st表并不在3100的考察范围内，而且有模板可背，这里就不再赘述了。

#include <bits/stdc++.h>
using namespace std;

const int N = int(1e5+10);

long F[N], S[N];
int n;
long m;

long dp[N][22];
int Log[N];
long sum[N];

void init()
{
	Log[0]=-1;
	for(int i=1;i<=n;i++)
		Log[i]=Log[i>>1]+1;
	for(int i=0;i<n;i++)
		dp[i][0]=S[i];
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
long query(int x,int y)
{
	int s=Log[y-x+1];
	return max(dp[x][s],dp[y-(1<<s)+1][s]);
}
int main()
{
	scanf("%d%ld", &n, &m);
	for(int i = 0; i < n; i++) scanf("%ld%ld", &F[i], &S[i]);
	sum[0] = F[0];
	for(int i = 1; i < n; i++) sum[i] = sum[i-1] + F[i];
	init();
	int p = 0, q = 0; // p in front; q back
	long res;
	for(int i = 0; i < n; i++) res = max(S[i], res);
	for(q = 0; q < n; q++)
	{
		while(p < n && sum[p]-sum[q-1] < m) p++;
		if(p < n) res = min(res, query(q, p-1));
	}
	printf("%ld\n", res);
	return 0;
}

Linyong GAN