单调队列

Monotonic Queue

简介

可以在$O(n + q)$的时间内，解决询问不互相包含的区间最值问题。

$n$ 是数组长度，$q$ 是询问个数。

询问的区间不能相互包含。

算法流程

将所有询问区间排序，从左向右依次处理。

参考题目

P1886 滑动窗口 /【模板】单调队列

https://www.luogu.com.cn/problem/P1886

题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is $[1,3,-1,-3,5,3,6,7]$, and $k = 3$。

输入格式

输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

样例 #1

样例输入 #1

8 3
1 3 -1 -3 5 3 6 7

样例输出 #1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

提示

【数据范围】
对于 $50\%$ 的数据，$1 \le n \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[1000020];
int q[1000020], b, f;
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	b = f = 0;
	for (int i = 1; i <= n; i++)
	{
		while (b < f && a[q[f - 1]] >= a[i])
		{
			f--;
		}
		q[f++] = i;
		while (q[b] <= i - m)
		{
			b++;
		}
		if (i >= m)
		{
			printf("%d%c", a[q[b]], i == n ? '\n' : ' ');
		}
	}
	b = f = 0;
	for (int i = 1; i <= n; i++)
	{
		while (b < f && a[q[f - 1]] <= a[i])
		{
			f--;
		}
		q[f++] = i;
		while (q[b] <= i - m)
		{
			b++;
		}
		if (i >= m)
		{
			printf("%d%c", a[q[b]], i == n ? '\n' : ' ');
		}
	}
}

题解

区间互不包含的最值问题
these intervals can not contain each other.

[1, 5]
[2, 3]
算作包含

[1, 5] contains [2, 3]

[1, 5]
[1, 3]
端点重合不算包含

[1, 5] does not contain [1, 3]

O(n + q)
数组长度 + 询问数
length of array + number of queries

双端队列
double-ended queue

一端进，两端出
push elements to the end of this queue
pop elements from both ends

最小值
for example, minimum

队列单调严格增加的
this queue should be strictly increasing

每次加入一个数字
each time we push an element

while (队列非空，队尾 > 当前数字)
删去队尾

while (queue is not empty, queue.back >= current element)
{
queue.pop()
}

[b, f)
b 队首
f 队尾，入队 q[f++] = i;
队列的大小 f - b
if (b < f) 那么队列非空

if (队列的第一个太早了)
{
删掉队列的第一个
}
队列中一定要存元素下标，而不是值

#include <bits/stdc++.h>
using namespace std;
int a[1000020];
int q[1000020];
// 队列q中存的是数组下标
int n, k, b, f;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    b = f = 0;
    for (int i = 0; i < k - 1; i++) {
       // 依次加入前k-1个元素
        while (b < f && a[q[f - 1]] >= a[i]) {
            f--;
        }
        // 如果新加入的元素a[i]比队尾的元素还小
        // 那么队尾的元素不再可能成为最小值，直接删去即可
        q[f++] = i;
        // 元素a[i]入队
    }
    for (int i = k - 1; i < n; i++) {
        if (q[b] <= i - k) {
            b++;
        }
        // 如果队首的元素位置过早，删去他；这里至多删一次，使用if即可
        while (b < f && a[q[f - 1]] >= a[i]) {
            f--;
        }
        // 如果新加入的元素a[i]比队尾的元素还小
        // 那么队尾的元素不再可能成为最小值，直接删去即可
        q[f++] = i;
        // 元素a[i]入队
        printf("%d%c", a[q[b]], i == n - 1 ? '\n' : ' ');
        // 当前的队首即为最小值
    }
    b = f = 0;
    for (int i = 0; i < k - 1; i++) {
        while (b < f && a[q[f - 1]] <= a[i]) {
            f--;
        }
        q[f++] = i;
    }
    for (int i = k - 1; i < n; i++) {
        if (q[b] <= i - k) {
            b++;
        }
        while (b < f && a[q[f - 1]] <= a[i]) {
            f--;
        }
        q[f++] = i;
        printf("%d%c", a[q[b]], i == n - 1 ? '\n' : ' ');
    }
}

P1440 求m区间内的最小值

https://www.luogu.com.cn/problem/P1440

题目描述

一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$。

输入格式

第一行两个整数，分别表示 $n$，$m$。

第二行，$n$ 个正整数，为所给定的数列 $a_i$。

输出格式

$n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i$ 之前 $m$ 个数的最小值。

样例 #1

样例输入 #1

6 2
7 8 1 4 3 2

样例输出 #1

0
7
7
1
1
3 

提示

对于 $100\%$ 的数据，保证 $1\le m\le n\le2\times10^6$，$1\le a_i\le3\times10^7$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[2000020];
int q[2000020], b, f;
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", a[q[b]]);
		scanf("%d", &a[i]);
		while (b < f && a[q[f - 1]] >= a[i])
		{
			f--;
		}
		q[f++] = i;
		while (q[b] <= i - m)
		{
			b++;
		}
	}
}

题解

P2034 选择数字

https://www.luogu.com.cn/problem/P2034

题目描述

给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入格式

第一行两个整数n，k

以下n行，每行一个整数表示a[i]。

输出格式

输出一个值表示答案。

样例 #1

样例输入 #1

5 2
1
2
3
4
5 

样例输出 #1

12

提示

对于20%的数据，n <= 10

对于另外20%的数据， k = 1

对于60%的数据，n <= 1000

对于100%的数据，1 <= n <= 100000，1 <= k <= n，0 <= 数字大小 <= 1,000,000,000

时间限制500ms

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long s;
int a[100020];
long long f[100020];
int q[100020], bb, ff;
int main()
{
	cin >> n >> m;
	q[ff++] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s += a[i];
		f[i] = f[q[bb]] + a[i];
		while (bb < ff && f[q[ff - 1]] > f[i])
		{
			ff--;
		}
		q[ff++] = i;
		while (bb < ff && q[bb] < i - m)
		{
			bb++;
		}
	}
	cout << s - f[q[bb]] << endl;
	return 0;
}

题解

P2627 / P2034

P2627 [USACO11OPEN]Mowing the Lawn G
P2034 选择数字
https://www.luogu.com.cn/problem/P2034
转化为选一些位置，不能有连续k+1个位置不选，最小化选取的和
choose some elements, minimize their sum.
the distance between two adjacent elements are at most k

a[0] = 0
a[n+1] = 0

位置 0 和 位置 n+1 一定选择
we must choose a[0] and a[n+1]

f[i] 选择了第 i 个位置，最小和是多少
f[i] if we choose i, the minimum sum is f[i]
答案是 sum - f[n+1]
答案是 sum - min(f[n], f[n-1], ..., f[n-m])
the answer is sum - f[n+1]
the answer is sum - min(f[n], f[n-1], ..., f[n-m])

f[i] = min(f[i-1], f[i-2], ... f[i-m-1]) + a[i]

当k=2时
when k = 2
f[3] = min(f[2], f[1], f[0]) + a[3] = 3
f[6] = min(f[5], f[4], f[3]) + a[6] = 3

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long s;
int a[100020];
long long f[100020];
int q[100020], bb, ff;
int main()
{
    cin >> n >> m;
    q[ff++] = 0; // f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s += a[i];
        f[i] = f[q[bb]] + a[i];
        while (bb < ff && f[q[ff - 1]] >= f[i])
        {
            ff--;
        }
        q[ff++] = i;
        if (q[bb] < i - m)
        {
            bb++;
        }
    }
    cout << s - f[q[bb]] << endl;
    return 0;
}

P2627 [USACO11OPEN]Mowing the Lawn G

https://www.luogu.com.cn/problem/P2627

题目描述

在一年前赢得了小镇的最佳草坪比赛后，Farmer John 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farmer John 希望能够再次夺冠。

然而，Farmer John 的草坪非常脏乱，因此，Farmer John 只能够让他的奶牛来完成这项工作。Farmer John 有 $N$（$1\le N\le 10^5$）只排成一排的奶牛，编号为 $1\ldots N$。每只奶牛的效率是不同的，奶牛 $i$ 的效率为 $E_i$（$0\le E_i\le 10^9$）。

靠近的奶牛们很熟悉，因此，如果 Farmer John安排超过 $K$ 只连续的奶牛，那么，这些奶牛就会罢工去开派对 😃。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过 $K$ 只奶牛。

输入格式

第一行：空格隔开的两个整数 $N$ 和 $K$。

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $E_i$。

输出格式

第一行：一个值，表示 Farmer John 可以得到的最大的效率值。

样例 #1

样例输入 #1

5 2
1
2
3
4
5

样例输出 #1

12

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long s;
int a[100020];
long long f[100020];
int q[100020], bb, ff;
int main()
{
	cin >> n >> m;
	q[ff++] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s += a[i];
		f[i] = f[q[bb]] + a[i];
		while (bb < ff && f[q[ff - 1]] > f[i])
		{
			ff--;
		}
		q[ff++] = i;
		while (bb < ff && q[bb] < i - m)
		{
			bb++;
		}
	}
	cout << s - f[q[bb]] << endl;
	return 0;
}

题解

P2627 / P2034

P2627 [USACO11OPEN]Mowing the Lawn G
P2034 选择数字
https://www.luogu.com.cn/problem/P2034
转化为选一些位置，不能有连续k+1个位置不选，最小化选取的和
choose some elements, minimize their sum.
the distance between two adjacent elements are at most k

a[0] = 0
a[n+1] = 0

位置 0 和 位置 n+1 一定选择
we must choose a[0] and a[n+1]

f[i] 选择了第 i 个位置，最小和是多少
f[i] if we choose i, the minimum sum is f[i]
答案是 sum - f[n+1]
答案是 sum - min(f[n], f[n-1], ..., f[n-m])
the answer is sum - f[n+1]
the answer is sum - min(f[n], f[n-1], ..., f[n-m])

f[i] = min(f[i-1], f[i-2], ... f[i-m-1]) + a[i]

当k=2时
when k = 2
f[3] = min(f[2], f[1], f[0]) + a[3] = 3
f[6] = min(f[5], f[4], f[3]) + a[6] = 3

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long s;
int a[100020];
long long f[100020];
int q[100020], bb, ff;
int main()
{
    cin >> n >> m;
    q[ff++] = 0; // f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s += a[i];
        f[i] = f[q[bb]] + a[i];
        while (bb < ff && f[q[ff - 1]] >= f[i])
        {
            ff--;
        }
        q[ff++] = i;
        if (q[bb] < i - m)
        {
            bb++;
        }
    }
    cout << s - f[q[bb]] << endl;
    return 0;
}

P3029 [USACO11NOV]Cow Lineup S

https://www.luogu.com.cn/problem/P3029

题目背景

【问题描述】

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置 X_i以及整数品种编号 ID_i表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一

系列照片中的最大和最小 X 坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站

在同一个地点的。

【输入格式】

第 1 行：牛的数量 N；

第 2..1+N 行：每行包含 2 个以空格分隔的正整数 X_i 和 ID_i；意义如题目描述；

【输出格式】

输出共一行，包含每个不同品种 ID 的照片的最低成本。

【输入样例】

6 25 7 26 1 15 1 22 3 20 1 30 1 【输出样例】

4 【输入说明】在不同的坐标点 25,26,15,22,20,30 中有六头牛

【输出说明】在约翰的牛中，从 X=22 到 X=26（整个规模为 4）包含了每个的不同品种的 ID 3，7 和 1。

【数据规模】

对于 50%的数据： 1≤N≤300；

对于 100%的数据：1≤N≤50,000；0≤X_i≤1,000,000,000；1≤ID_i≤1,000,000,000；

感谢uid=15936的翻译

题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

依次给出N头牛的位置及种类，要求找出连续一段，使其中包含所有种类的牛，问：这连续的一段最小长度是多少？

输入格式

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.

输出格式

* Line 1: The smallest cost of a photograph containing each distinct breed ID.

样例 #1

样例输入 #1

6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1 

样例输出 #1

4 

提示

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.

感谢 wjcwinmt 提供题目简述

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
map<int, int> c;
int n, cnt, z = 1e9;
pair<int, int> a[50020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first >> a[i].second;
		s.insert(a[i].second);
	}
	sort(a, a + n);
	for (int i = 0, j = 0; i < n;)
	{
		while (j < n && cnt < s.size())
		{
			cnt += !c[a[j++].second]++;
		}
		if (cnt == s.size())
		{
			z = min(z, a[j-1].first - a[i].first);
		}
		cnt -= !--c[a[i++].second];
	}
	printf("%d\n", z);
	return 0;
}

题解

双指针法 尺取法

对于每个起点（左端点）可以求出最优解（右端点）

如果左端点向右移动，右端点要么不动，要么向右移动

满足这个条件就可以用双指针法解决

#include <bits/stdc++.h>
using namespace std;
set<int> s;
map<int, int> c;
int n, cnt, z = 1e9;
pair<int, int> a[50020];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first >> a[i].second;
        s.insert(a[i].second);
    }
    sort(a, a + n);
    // cnt 当前区间内，牛的种类数
    // c 当前区间内，每种牛的个数
    for (int i = 0, j = 0; i < n;) // 下标范围 [i, j)   区间长度 a[j-1].first - a[i].first
    {
        while (j < n && cnt < s.size())
        {
            cnt += !c[a[j++].second]++;
            // if (!c[a[j].second])
            // {
            //     cnt++;
            // }
            // c[a[j].second]++;
            // j++;
        }
        if (cnt == s.size()) // 如果所有的种类都在
        {
            z = min(z, a[j-1].first - a[i].first);
            // 用当前区间长度更新答案
        }
        // 删去第i个牛
        cnt -= !--c[a[i++].second];
        // --c[a[i].second];
        // if (!c[a[i].second])
        // {
        //     cnt--;
        // }
        // i++;
    }
    printf("%d\n", z);
    return 0;
}

cnt += !c[a[j++].second]++;
if (c[a[j].second] == 0)
{
    cnt += 1;
}
c[a[j].second] += 1
j += 1;


cnt -= !--c[a[i++].second];
--c[a[i].second];
if (c[i].second == 0)
{
    cnt -= 1;
}
i++;

P3069 [USACO13JAN]Cow Lineup G

https://www.luogu.com.cn/problem/P3069

题目描述

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row. Each cow is identified by an integer "breed ID" in the range 0...1,000,000,000; the breed ID of the ith cow in the lineup is B(i). Multiple cows can share the same breed ID.

FJ thinks that his line of cows will look much more impressive if there is a large contiguous block of cows that all have the same breed ID. In order to create such a block, FJ chooses up to K breed IDs and removes from his lineup all the cows having those IDs. Please help FJ figure out the length of the largest consecutive block of cows with the same breed ID that he can create by doing this.

农夫约翰的N(1 <= N <= 100,000)只奶牛排成了一队，每只牛都用编上了一个“血统编号”，该编号为范围0...1,000,000,000的整数。血统相同的奶牛有相同的编号，也就是可能有多头奶牛是相同的"血统编号"。

约翰觉得如果连续排列的一段奶牛有相同的血统编号的话，奶牛们看起来会更具有威猛。为了创造这样的连续段，约翰最多能选出k种血统的奶牛，并把他们全部从队列中赶走。

请帮助约翰计算这样做能得到的由相同血统编号的牛构成的连续段的长度最大是多少？

输入格式

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Line i+1 contains the breed ID B(i).

输出格式

* Line 1: The largest size of a contiguous block of cows with

identical breed IDs that FJ can create.

样例 #1

样例输入 #1

9 1 
2 
7 
3 
7 
7 
3 
7 
5 
7 

样例输出 #1

4 

提示

There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7. FJ would like to remove up to 1 breed ID from this lineup.

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7, 5, 7. In this new lineup, there is a contiguous block of 4 cows with the same breed ID (7).

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> c;
int n, m, z, cnt;
int a[100020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, j = 0; j < n; j++)
	{
		scanf("%d", &a[j]);
		cnt += !c[a[j]]++;
		while (cnt > m + 1)
		{
			cnt -= !--c[a[i++]];
		}
		z = max(z, c[a[j]]);
	}
	printf("%d\n", z);
	return 0;
}

题解

#include <bits/stdc++.h>
using namespace std;
map<int, int> c;
int n, m, z, cnt;
int a[100020];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0, j = 0; j < n; j++) // j 是右端点
    {
        scanf("%d", &a[j]);
        cnt += !c[a[j]]++;
        // if (!c[a[j]])
        // {
        //     cnt++;
        // }
        // c[a[j]]++；
        while (cnt > m + 1) // while [i, j] 区间内的牛种类数太多了，> m+1
        {
            cnt -= !--c[a[i++]];
            // 删去第i个牛
            // --c[a[i]];
            // if (!c[a[i]])
            // {
            //     cnt--;
            // }
            // i++;
        }
        z = max(z, c[a[j]]);
        // 如果我们选择 [i, j] 区间，我们认为 a[j] 这种牛出现次数最多，用 a[j] 出现的次数更新答案
    }
    printf("%d\n", z);
    return 0;
}

P4085 [USACO17DEC]Haybale Feast G

https://www.luogu.com.cn/problem/P4085

题目描述

Farmer John is preparing a delicious meal for his cows! In his barn, he has $N$ haybales ($1 \le N \le 100,000$). The $i$th haybale has a certain flavor $F_i$ ($1 \le F_i \le 10^9$) and a certain spiciness $S_i$ ($1 \le S_i \le 10^9$).

The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.

Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least $M$ ($1 \le M \le 10^{18}$).

输入格式

The first line contains the integers $N$ and $M$, the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$.

输出格式

Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

样例 #1

样例输入 #1

5 10
4 10
6 15
3 5
4 9
3 6

样例输出 #1

9

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z = 1e9;
long long m, s;
int a[100020];
int b[100020];
int q[100020], bb, ff;
int main()
{
	cin >> n >> m;
	for (int i = 0, j = 0; j < n; j++)
	{
		cin >> a[j] >> b[j];
		s += a[j];
		while (bb < ff && b[q[ff - 1]] < b[j])
		{
			ff--;
		}
		q[ff++] = j;
		while (s - a[i] >= m)
		{
			s -= a[i++];
		}
		while (bb < ff && q[bb] < i)
		{
			bb++;
		}
		if (s >= m)
		{
			z = min(z, b[q[bb]]);
		}
	}
	cout << z << endl;
	return 0;
}

题解

双指针法 结合 单调队列

下面的方法很麻烦
for (右端点)
{
while (如果左端点往右移动后还满足)
{
左端点往右移动
}
if (满足条件)
{
更新答案
}
右端点右移
}

#include <bits/stdc++.h>
using namespace std;
int n, z = 1e9;
long long m, s;
int a[100020];
int b[100020];
int q[100020], bb, ff;
int main()
{
    cin >> n >> m;
    for (int i = 0, j = 0; j < n; j++) // 枚举右端点 j
    {
        cin >> a[j] >> b[j];
        // 加入 j
        s += a[j]; // 维护和
        // 维护单调队列
        while (bb < ff && b[q[ff - 1]] < b[j])
        {
            ff--;
        }
        q[ff++] = j;
        while (s - a[i] >= m) // 如果左端点往右移动后还满足
        {
            s -= a[i++]; // 左端点往右移动
        }
        while (bb < ff && q[bb] < i) // 把单调队列中不在 [i, j] 区间的删掉
        {
            bb++;
        }
        if (s >= m) // 如果和满足条件，更新答案
        {
            z = min(z, b[q[bb]]);
        }
    }
    cout << z << endl;
    return 0;
}

P2698 [USACO12MAR]Flowerpot S

https://www.luogu.com.cn/problem/P2698

题目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John's flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。

每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。

我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

输入格式

第一行2个整数 N 和 D。

第2.. N+1行每行2个整数，表示水滴的坐标(x,y)。

输出格式

仅一行1个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在D单位的时间接住满足要求的水滴，则输出-1。

样例 #1

样例输入 #1

4 5
6 3
2 4
4 10
12 15

样例输出 #1

2

提示

【样例解释】

有4滴水， (6,3), (2,4), (4,10), (12,15).水滴必须用至少5秒时间落入花盆。花盆的宽度为2是必须且足够的。把花盆放在x=4..6的位置，它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。

【数据范围】

40%的数据：1 ≤ N ≤ 1000，1 ≤ D ≤ 2000；

100%的数据：1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤10^6。

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
int n, d;
int q1[100020], b1, f1;
int q2[100020], b2, f2;
int main()
{
	scanf("%d%d", &n, &d);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	int z = 1e9;
	for (int i = 0, j = 0; i < n; i++)
	{
		while (b1 < f1 && q1[b1] < i)
		{
			b1++;
		}
		while (b2 < f2 && q2[b2] < i)
		{
			b2++;
		}
		while (a[q1[b1]].second - a[q2[b2]].second < d && j < n)
		{
			while (b1 < f1 && a[q1[f1 - 1]].second <= a[j].second)
			{
				f1--;
			}
			while (b2 < f2 && a[q2[f2 - 1]].second >= a[j].second)
			{
				f2--;
			}
			q1[f1++] = j;
			q2[f2++] = j++;
		}
		if (a[q1[b1]].second - a[q2[b2]].second >= d)
		{
			z = min(z, a[j-1].first - a[i].first);
		}
	}
	printf("%d\n", z > 1e8 ? -1 : z);
	return 0;
}

题解

P2949 [USACO09OPEN]Work Scheduling G

https://www.luogu.com.cn/problem/P2949

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

样例 #1

样例输入 #1

3 
2 10 
1 5 
1 7 

样例输出 #1

17 

提示

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int> > q;
pair<int, int> a[100020];
long long z;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += a[i].second;
		q.push(a[i].second);
		if (q.size() > a[i].first)
		{
			z -= q.top();
			q.pop();
		}
	}
	printf("%lld\n", z);
	return 0;
}

题解

带反悔的贪心

假设决定了做哪些任务，一定是按照截止时间排序来做。
对于任意一个时间x，
截止时间<=x的任务 消耗的总时间 必须<=x
截止时间<=x的任务 个数 必须<=x

扫描所有任务，每次直接选择，如果当前选择的任务个数 > 截止时间，在所有已经选择的任务中，
扔掉获利最小的（扔掉获利最小的任务时，不考虑截止时间）

假设每个任务消耗的时间不相同
可以用背包解决
先排序
每个任务更新时，只更新到自己的截止时间

背包时，不同物品的放置顺序是有关系的
先考虑假设要选择一个集合
按哪种顺序一定可以放置成功
先把这些物品按照这个顺序排序

P3088 [USACO13NOV]Crowded Cows S

https://www.luogu.com.cn/problem/P3088

题目描述

Farmer John's N cows (1 <= N <= 50,000) are grazing along a one-dimensional fence. Cow i is standing at location x(i) and has height h(i) (1 <= x(i),h(i) <= 1,000,000,000).

A cow feels "crowded" if there is another cow at least twice her height within distance D on her left, and also another cow at least twice her height within distance D on her right (1 <= D <= 1,000,000,000). Since crowded cows produce less milk, Farmer John would like to count the number of such cows. Please help him.

FJ有N(1 <= N <= 50,000)头奶牛沿着一维的栅栏吃草，第i头奶牛在目标点x(i) ，它的身高是 h(i) (1 <=x(i),h(i) <= 1,000,000,000)。

当一头奶牛左边D距离内而且右边D距离内有身高至少是它的两倍的奶牛，t (1 <= D <= 1,000,000,000)，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

输入格式

* Line 1: Two integers, N and D.

* Lines 2..1+N: Line i+1 contains the integers x(i) and h(i). The locations of all N cows are distinct.

输出格式

* Line 1: The number of crowded cows.

样例 #1

样例输入 #1

6 4 
10 3 
6 2 
5 3 
9 7 
3 6 
11 2 

样例输出 #1

2 

提示

There are 6 cows, with a distance threshold of 4 for feeling crowded. Cow #1 lives at position x=10 and has height h=3, and so on.

The cows at positions x=5 and x=6 are both crowded.

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[50020];
int ql[50020], bl, fl;
int qr[50020], br, fr;
int n, d, z;
int main()
{
	scanf("%d%d", &n, &d);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0, jl = 0, jr = 0; i < n; i++)
	{
		while (jl < n && a[jl].first <= a[i].first)
		{
			while (bl < fl && a[ql[fl - 1]].second <= a[jl].second)
			{
				fl--;
			}
			ql[fl++] = jl++;
		}
		while (jr < n && a[jr].first <= a[i].first + d)
		{
			while (br < fr && a[qr[fr - 1]].second <= a[jr].second)
			{
				fr--;
			}
			qr[fr++] = jr++;
		}
		while (a[ql[bl]].first < a[i].first - d)
		{
			bl++;
		}
		while (a[qr[br]].first < a[i].first)
		{
			br++;
		}
		if (min(a[qr[br]].second, a[ql[bl]].second) >= a[i].second * 2)
		{
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[50020];
int ql[50020], bl, fl;
int qr[50020], br, fr;
int n, d, z;
int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].first, &a[i].second);
    }
    sort(a, a + n);
    for (int i = 0, jl = 0, jr = 0; i < n; i++)
    {
        // jl 左边区间[ a[i].first - d, a[i].first ] 枚举到第几个牛了 （只会加一个）
        while (jl < n && a[jl].first <= a[i].first)
        {
            // 第 jl 个牛在左边区间内，加入左边区间
            while (bl < fl && a[ql[fl - 1]].second <= a[jl].second)
            {
                fl--;
            }
            ql[fl++] = jl++;
        }
        // jl 左边区间[ a[i].first, a[i].first + d ] 枚举到第几个牛了 （可能加多个）
        while (jr < n && a[jr].first <= a[i].first + d)
        {
            // 第 jr 个牛，在右边区间，加入右边区间
            while (br < fr && a[qr[fr - 1]].second <= a[jr].second)
            {
                fr--;
            }
            qr[fr++] = jr++;
        }
        // 如果 左边区间队首的牛已经 不在 [ a[i].first - d, a[i].first ]
        // 那么就删掉（可能删多个）
        while (a[ql[bl]].first < a[i].first - d)
        {
            bl++;
        }
        // 如果 右边区间队首的牛已经 不在 [ a[i].first, a[i].first + d]
        // 那么就删掉（只会删一个）
        while (a[qr[br]].first < a[i].first)
        {
            br++;
        }
        // min(左边最大, 右边最大) >= 自己的二倍
        if (min(a[qr[br]].second, a[ql[bl]].second) >= a[i].second * 2)
        {
            z++;
        }
    }
    printf("%d\n", z);
    return 0;
}

P1419 寻找段落

https://www.luogu.com.cn/problem/P1419

题目描述

给定一个长度为 $n$ 的序列 $a$，定义 $a_i$ 为第 $i$ 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 $[S, T]$ 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行两个整数 $S$ 和 $T$，表示段落长度的范围，在 $[S, T]$ 之间。

第三行到第 $n+2$ 行，每行一个整数表示每个元素的价值指数。

输出格式

一个实数，保留 $3$ 位小数，表示最优段落的平均值。

样例 #1

样例输入 #1

3
2 2
3
-1
2

样例输出 #1

1.000

提示

【数据范围】

对于 $30\%$ 的数据有 $n \le 1000$。

对于 $100\%$ 的数据有 $1 \le n \le 100000$，$1 \le S \le T \le n$，$-{10}^4 \le a_i \le {10}^4$。

【题目来源】

tinylic 改编

参考代码

题解

P1714 切蛋糕

https://www.luogu.com.cn/problem/P1714

题目描述

今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 $n$ 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 $m(m\le n)$ 小块的蛋糕。

请你帮他从这 $n$ 小块中找出连续的 $k(1 \le k\le m)$ 块蛋糕，使得其上的总幸运值最大。

形式化地，在数列 $\{p_n\}$ 中，找出一个子段 $[l,r](r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。

输入格式

第一行两个整数 $n,m$。分别代表共有 $n$ 小块蛋糕，小 Z 最多只能吃 $m$ 小块。

第二行 $n$ 个整数，第 $i$ 个整数 $p_i$ 代表第 $i$ 小块蛋糕的幸运值。

输出格式

仅一行一个整数，即小 Z 能够得到的最大幸运值。

样例 #1

样例输入 #1

5 2
1 2 3 4 5

样例输出 #1

9

样例 #2

样例输入 #2

6 3
1 -2 3 -4 5 -6

样例输出 #2

5

提示

数据规模与约定

• 对于 $20\%$ 的数据，有 $1\le n\le100$。
• 对于 $100\%$ 的数据，有 $1\le n\le5\times 10^5$，$|p_i|≤500$。

保证答案的绝对值在 $[0,2^{31}-1]$ 之内。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, z = -2e9;
int s[500020];
int q[500020], b, f;
int main()
{
	cin >> n >> m;
	q[f++] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
		s[i] += s[i - 1];
		while (b < f && q[b] < i - m)
		{
			b++;
		}
		z = max(z, s[i] - s[q[b]]);
		while (b < f && s[q[f - 1]] > s[i])
		{
			f--;
		}
		q[f++] = i;
	}
	cout << z << endl;
	return 0;
}

题解

求前缀和 s[i] 前 i 个数字的和

枚举区间的右端点 i

如果左端点是 j， 那么区间长度是 i - j
区间的和 a[j+1] + a[j+2] + ... + a[i] = s[i] - s[j]

s[i] - s[j] (i - m <= j < i)

#include <bits/stdc++.h>
using namespace std;
int n, m, z = -2e9;
int s[500020];
int q[500020], b, f;
int main()
{
    cin >> n >> m;
    q[f++] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
        // 删除 < i - m 的部分
        while (b < f && q[b] < i - m)
        {
            b++;
        }
        // s[i] - min(s[i-1], s[i-2], ..., s[i-m]);
        // 得到的就是以 a[i] 为最后一个元素的最优解
        z = max(z, s[i] - s[q[b]]);
        // s[i] 加入队列
        while (b < f && s[q[f - 1]] > s[i])
        {
            f--;
        }
        q[f++] = i;
    }
    cout << z << endl;
    return 0;
}

P1725 琪露诺

https://www.luogu.com.cn/problem/P1725

题目描述

在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。

某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。

小河可以看作一列格子依次编号为 $0$ 到 $N$，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 $i$ 时，她只移动到区间 $[i+L,i+R]$ 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。

每一个格子都有一个冰冻指数 $A_i$，编号为 $0$ 的格子冰冻指数为 $0$。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 $A_i$。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。

开始时，琪露诺在编号 $0$ 的格子上，只要她下一步的位置编号大于 $N$ 就算到达对岸。

输入格式

第一行三个正整数 $N, L, R$。

第二行共 $N+1$ 个整数，第 $i$ 个数表示编号为 $i-1$ 的格子的冰冻指数 $A_{i-1}$。

输出格式

一个整数，表示最大冰冻指数。

样例 #1

样例输入 #1

5 2 3
0 12 3 11 7 -2

样例输出 #1

11

提示

对于 $60\%$ 的数据，$N \le 10^4$。

对于 $100\%$ 的数据，$N \le 2\times 10^5$，$-10^3 \le A_i\le 10^3$，$1 \le L \le R \le N$。数据保证最终答案不超过 $2^{31}-1$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, l, r, z = -2e9;
int a[200020];
int f[200020];
int q[200020], bb, ff;
int main()
{
	cin >> n >> l >> r;
	memset(f, 0xc0, sizeof f);
	f[0] = 0;
	for (int i = 0; i <= n; i++)
	{
		if (i >= l)
		{
			while (bb < ff && f[q[ff - 1]] < f[i - l])
			{
				ff--;
			}
			q[ff++] = i-l;
		}
		cin >> a[i];
		while (bb < ff && q[bb] < i - r)
		{
			bb++;
		}
		if (bb < ff)
		{
			f[i] = f[q[bb]] + a[i];
		}
		if (i > n - r)
		{
			z = max(z, f[i]);
		}
	}
	cout << z << endl;
	return 0;
}

题解

P2032 扫描

https://www.luogu.com.cn/problem/P2032

题目描述

有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。

现在给你一个可以盖住连续 $k$ 个数的木板。

一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

输入格式

第一行两个整数 $n,k$，表示共有 $n$ 个数，木板可以盖住 $k$ 个数。

第二行 $n$ 个整数，表示矩阵中的元素。

输出格式

共 $n - k + 1$ 行，每行一个整数。

第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。

样例 #1

样例输入 #1

5 3
1 5 3 4 2

样例输出 #1

5
5
4

提示

对于 $20\%$ 的数据，$1 \leq k \leq n \leq 10^3$。

对于 $50\%$ 的数据，$1 \leq k \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[2000020];
int q[2000020], b, f;
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	b = f = 0;
	for (int i = 1; i <= n; i++)
	{
		while (b < f && a[q[f - 1]] <= a[i])
		{
			f--;
		}
		q[f++] = i;
		while (q[b] <= i - m)
		{
			b++;
		}
		if (i >= m)
		{
			printf("%d\n", a[q[b]]);
		}
	}
}

题解

P3957 [NOIP2017 普及组] 跳房子

https://www.luogu.com.cn/problem/P3957

题目背景

NOIP2017 普及组 T4

题目描述

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 $R$ 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 $d$ 。小 $R$ 希望改进他的机器人，如果他花 $g$ 个金币改进他的机器人，那么他的机器人灵活性就能增加 $g$ ，但是需要注意的是，每 次弹跳的距离至少为 $1$ 。具体而言，当 $g<d$ 时，他的机器人每次可以选择向右弹跳的距离为 $d-g,d-g+1,d-g+2$ ，…， $d+g-2$ ， $d+g-1$ ， $d+g$ ；否则（当 $g \geq d$ 时），他的机器人每次可以选择向右弹跳的距离为 $1$ ， $2$ ， $3$ ，…， $d+g-2$ ， $d+g-1$ ， $d+g$ 。

现在小 $R$ 希望获得至少 $k$ 分，请问他至少要花多少金币来改造他的机器人。

输入格式

第一行三个正整数 $n$ ， $d$ ， $k$ ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 $n$ 行，每行两个整数 $x_i,s_i$ ，分别表示起点到第 $i$ 个格子的距离以及第 $i$ 个格子的分数。两个数之间用一个空格隔开。保证 $x_i$ 按递增顺序输入。

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 $k$ 分，输出 $-1$ 。

样例 #1

样例输入 #1

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #1

2

样例 #2

样例输入 #2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #2

-1

提示

【输入输出样例 1 说明】
$2$个金币改进后, 小 R 的机器人依次选择的向右弹跳的距离分别为$2, 3, 5, 3, 4,3$, 先后到达的位置分别为 $2, 5, 10, 13, 17, 20$, 对应$1, 2, 3, 5, 6, 7$ 这$6$ 个格子。这些格子中的数字之和$15$ 即为小 R 获得的分数。

输入输出样例 2 说明

由于样例中 $7$ 个格子组合的最大可能数字之和只有 $18$ ,无论如何都无法获得$20$分

数据规模与约定

本题共 10 组测试数据,每组数据 10 分。

对于全部的数据满足$1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ x_i, k ≤ 10^9, |s_i| < 10^5$。

对于第 $1, 2$组测试数据, $n ≤ 10$；

对于第$3, 4, 5$ 组测试数据, $n ≤ 500$

对于第$6, 7, 8$ 组测试数据, $d = 1$

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, d, k;
int x[500020];
int s[500020];
int q[500020], b, f;
long long g[500020];
long long calc(int M) {
	int L = max(1, d - M);
	int R = d + M;
	long long re = 0;
	b = f = 0;
	for (int i = 1, j = 0; i <= n; i++) {
		while (j <= n && x[i] - x[j] >= L) {
			while (b < f && g[j] > g[q[f - 1]]) {
				f--;
			}
			q[f++] = j++;
		}
		while (b < f && x[i] - x[q[b]] > R) {
			b++;
		}
		if (b < f) {
			g[i] = g[q[b]] + s[i];
		} else {
			g[i] = -1e18;
		}
		re = max(re, g[i]);
	}
	return re;
}
int main() {
	scanf("%d%d%d", &n, &d, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x[i], &s[i]);
	}
	int L = -1, R = 1000000007;
	while (L < R - 1) {
		int M = (L + R) / 2;
		if (calc(M) >= k) {
			R = M;
		} else {
			L = M;
		}
	}
	if (R == 1000000007) {
		printf("-1\n");
	} else {
		printf("%d\n", R);
	}
	return 0;
}

题解

花的金币越多
选择越多
得分越高

第一步，二分花多少金币
第二个，给定金币个数，计算最高得分

#include <bits/stdc++.h>
using namespace std;
int n, d, k;
int x[500020];
int s[500020];
int q[500020], b, f;
long long g[500020];
long long calc(int M) { // M 个金币最高得分
    int L = max(1, d - M);
    int R = d + M;
    // 跳跃范围 [L, R]
    // 想跳到 x[i] 起点的范围是 x[i] - R <= x[j] <= x[i] - L
    long long re = 0;
    b = f = 0;
    for (int i = 1, j = 0; i <= n; i++) {
        // 如果 x[j] <= x[i] - L 那么就加入单调队列
        while (j <= n && x[i] - x[j] >= L) {
            while (b < f && g[j] > g[q[f - 1]]) {
                f--;
            }
            q[f++] = j++;
            // 即使 g[j] 是不合法的状态-1e18，也会被加入单调队列用来更新其他节点
        }
        // 当 队首 < x[i] - R 就 删掉
        while (b < f && x[i] - x[q[b]] > R) {
            b++;
        }
        if (b < f) {
            g[i] = g[q[b]] + s[i];
        } else {
            g[i] = -1e18; // 起点到不了当前状态，当前状态不合法
        }
        re = max(re, g[i]); // 找所有终点的最大值
    }
    return re;
}
int main() {
    scanf("%d%d%d", &n, &d, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &s[i]);
    }
    int L = -1, R = 1000000007;
    while (L < R - 1) {
        int M = (L + R) / 2;
        if (calc(M) >= k) {
            R = M;
        } else {
            L = M;
        }
    }
    if (R == 1000000007) {
        printf("-1\n");
    } else {
        printf("%d\n", R);
    }
    return 0;
}

P4544 [USACO10NOV]Buying Feed G

https://www.luogu.com.cn/problem/P4544

题目描述

约翰开车来到镇上，他要带$K$吨饲料回家。运送饲料是需要花钱的，如果他的车上有$X$吨饲料，每公里就要花费$X^2$元，开车D公里就需要$D\times X^2$元。约翰可以从$N$家商店购买饲料，所有商店都在一个坐标轴上，第$i$家店的位置是$X_i$，饲料的售价为每吨$C_i$元，库存为$F_i$。

约翰从坐标$X=0$开始沿坐标轴正方向前进，他家在坐标$X=E$上。为了带$K$吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于$K$。

举个例子，假设有三家商店，情况如下所示：

坐标	$X=1$	$X=3$	$X=4$	$E=5$
库存	$1$	$1$	$1$
售价	$1$	$2$	$2$

如果$K=2$，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是$1+4=5$，花在商店的钱是$2+2=4$，共需要$9$元。

输入格式

第$1$行:三个整数$K,E,N$ 第$2..N+1$行:第$i+1$行的三个整数代表,$X_i,F_i,C_i$.

输出格式

一个整数,代表最小花费

样例 #1

样例输入 #1

2 5 3
3 1 2
4 1 2
1 1 1

样例输出 #1

9

提示

$1 \leq K \leq 10000 , 1 \leq E \leq 500 , 1 \leq N \leq 500$

$0 < Xi < E, 1 \leq Fi \leq 10000, 1 \leq C_i \leq 10^7$

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l;
long long f[10020];
pair<int, pair<int, int> > a[520];
void gao(int x, long long y)
{
	for (int i = m; i >= x; i--)
	{
		f[i] = min(f[i], f[i - x] + y);
	}
}
int main()
{
	scanf("%d%d%d", &m, &l, &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
	}
	sort(a, a + n);
	a[n].first = l;
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= a[i].second.first; j *= 2)
		{
			a[i].second.first -= j;
			gao(j, (long long)j * a[i].second.second);
		}
		gao(a[i].second.first, (long long)a[i].second.first * a[i].second.second);
		for (int j = 0; j <= m; j++)
		{
			f[j] += (long long)j * j * (a[i + 1].first - a[i].first);
		}
	}
	printf("%lld\n", f[m]);
	return 0;
}

题解

f[i][j] 到 位置i 携带 j 的饲料，最小花费
如果i位置没有商店，那么直接f[i][j] = f[i-1][j] + j * j
如果i位置有商店，那么直接f[i][j] = min(f[i-1][j] + j * j, f[i][j - k] + k * 单价) 在i位置买k的饲料

上限 100 个， 100 个 零一背包

100 = 1 + 2 + 4 + 8 + 16 + 32 + 37

5 * 1
5 * 2
5 * 4
5 * 8
5 * 16
5 * 32
5 * 37

f[i][j] min cost at position i, j units of feed.
if there is no shop at i,
f[i][j] = f[i-1][j] + j * j;

if there is a shop at i,
we should do knapsack on f[i]

2. monotonic queue

do weight times monotonic queue, each with length (size/weight)

weight = 2
value = v
limit = 3;

f[13] = max(f[13], f[11] + v, f[9] + v * 2, f[7] + v * 3)
f[11] = max(f[11], f[ 9] + v, f[7] + v * 2, f[5] + v * 3)
f[9]  = max(f[ 9], f[ 7] + v, f[5] + v * 2, f[3] + v * 3)
f[7]  = max(f[ 7], f[ 5] + v, f[3] + v * 2, f[1] + v * 3)

f[13] = max(f[13]-6*v, f[11]-5*v, f[9]-4*v, f[7]-3*v) + 6*v;
f[11] = max(f[11]-5*v, f[ 9]-4*v, f[7]-3*v, f[5]-2*v) + 5*v;
f[9]  = max(f[ 9]-4*v, f[ 7]-3*v, f[5]-2*v, f[3]-1*v) + 4*v;
f[7]  = max(f[ 7]-3*v, f[ 5]-2*v, f[3]-1*v, f[1]-0*v) + 3*v;

f[1]-0*v, f[3]-1*v, f[5]-2*v, f[7]-3*v, f[9]-4*v, f[11]-5*v, f[13]-6*v
f[0]-0*v, f[2]-1*v, f[4]-2*v, f[6]-3*v, f[8]-4*v, f[10]-5*v, f[12]-6*v

P5202 [USACO19JAN]Redistricting P

https://www.luogu.com.cn/problem/P5202

题目背景

USACO 19年一月月赛铂金组第一题

题目描述

奶牛们的特大城市，牛都，要进行重新分区了！——这总是一个在居住在这里的两大主要种族（荷斯坦牛和更赛牛）之间富有争议的政治事件，因为两大种族都想要在牛都政府中保持足够的影响力。

牛都的大都市圈由一列 $n$ 块牧草地组成，每块里有一头奶牛，均为荷斯坦牛 (Holstein) 和更赛牛 (Guernsey) 之一。

牛都政府想要将大都市圈划分为若干个连续的区，使得每个区至少包含一块牧草地且至多包含 $k$ 块牧草地，并且每块牧草地恰好属于一个区。由于政府当前由荷斯坦牛控制，她们想要找到一种分区方式能够最小化更赛牛较多或者均势的区的数量（如果更赛牛的数量与荷斯坦牛的数量相等那么这个区就是均势的）。

有一个关心政治的更赛牛团体想要知道政府的分区计划可能会对她们造成多少损害。帮助她们求出最坏情况，也就是更赛牛较多或是均势的区的最小可能的数量。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表牧草地的个数 $n$ 和每个区包含草地的上限 $k$。

输入的第二行是一个长度为 $n$ 的字符串 $s$，$s$ 中只含字符 H 和 G。若 $s$ 的第 $i$ 个字符是 H，则代表第 $i$ 块草地上的奶牛是荷斯坦牛，否则是更赛牛。

输出格式

输出一行一个整数，代表更赛牛较多或者优势区的最小可能数量。

样例 #1

样例输入 #1

7 2
HGHGGHG

样例输出 #1

3

提示

样例解释

一种可能的划分方式是 $[1],~[2, 3],~[4, 5],~[6, 7]$。第二、四个区是均势的区，第三个区是更赛牛优势的区。

数据范围

对于 $100\%$ 的数据，保证 $1 \leq k \leq n \leq 3 \times 10^5$，$s$ 的长度为 $n$，且只含字符 H 和 G。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, b, f;
int q[300020];
int g[300020];
int s[300020];
char c[300020];
int main() {
	scanf("%d%d%s", &n, &m, c);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] + (c[i] == 'H' ? 1 : -1);
	}
	q[f++] = 0;
	for (int i = 1; i <= n; i++) {
		while (q[b] < i - m) {
			b++;
		}
		g[i] = g[q[b]] + (s[i] - s[q[b]] <= 0);
		while (b < f && make_pair(g[q[f - 1]], s[q[f - 1]]) >= make_pair(g[i], s[i])) {
			f--;
		}
		q[f++] = i;
	}
	printf("%d\n", g[n]);
	return 0;
}

题解

下标从1开始
每个区最大包含 m 个字符

g[i] 表示前i个划区 G >= H 最少几个区？
g[i] for the first i pastures, the minimum number of distrcts (G >= H)

s[i] 表示 前i个， H 的个数 - G 的个数
s[i] for the first i pastures, the number of H - the number of G

g[i-m] g[i-m+1] ... g[i-1] -> g[i]
从哪个位置转移最好呢？

首先 f 越小越好，如果 f 一样，s 越小越好
如果 f 小了，后面的 s 最差情况下，也就是 + 1

决定从 i - j 转移 (1 <= j <= m)

g[i] = min(g[i], g[i - j] + (s[i] - s[i - j] <= 0))

如果 s[i] <= s[i - j] 就意味着从 i-j+1, i-j+2, ..., i 这些共j个数字中，H 的个数 <= G 的个数

找到最小的 (g[i-j], s[i-j]) (1 <= j <= m)
minimze the pair (g[i-j], s[i-j]) (1 <= j <= m)

#include <bits/stdc++.h>
using namespace std;
int n, m, b, f;
int q[300020];
int g[300020];
int s[300020];
char c[300020];
int main() {
    scanf("%d%d%s", &n, &m, c);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + (c[i] == 'H' ? 1 : -1);
    }
    q[f++] = 0; // (g[0], s[0])
    for (int i = 1; i <= n; i++) {
        while (q[b] < i - m) {
            b++;
        }
        // 从 q[b] 转移到 i
        g[i] = g[q[b]] + (s[i] - s[q[b]] <= 0);
        // 新状态 (g[i], s[i]) 入队
        while (b < f && make_pair(g[q[f - 1]], s[q[f - 1]]) >= make_pair(g[i], s[i])) {
            f--;
        }
        q[f++] = i;
    }
    printf("%d\n", g[n]);
    return 0;
}

spoj FESTIVAL

https://www.spoj.com/problems/FESTIVAL/

spoj ADASQR

https://www.spoj.com/problems/ADASQR/

参考资料