【滑动窗口】P4085 [USACO17DEC] Haybale Feast G|普及+
本文涉及知识点
C++算法：滑动窗口及双指针总结
[USACO17DEC] Haybale Feast G
题面翻译
题目描述
农夫约翰正在为他的奶牛准备一顿美味的晚餐！在他的谷仓里，他有 N N N 个干草捆 ( 1 ≤ N ≤ 1 0 5 ) (1 \le N \le 10^5) (1≤N≤105) 。第 i i i 个干草捆有一定的风味 F i ( 1 ≤ F i ≤ 1 0 9 ) F_i(1 \le F_i \le 10^9) Fi(1≤Fi≤109) 和一定的辣度 S i ( 1 ≤ S i ≤ 1 0 9 ) S_i(1 \le S_i \le 10^9) Si(1≤Si≤109) 。
这顿饭将由一道菜组成，是一个连续的区间，包含一个或多个连续的干草捆(农夫约翰不能改变干草捆的顺序)。这顿饭的总体的风味是这段区间里风味的总和。这顿饭的总体辣度是区间中所有草包的最大辣度。
农夫约翰想确定他的这道菜所能达到的最小辣度，但是这道菜的总风味必须至少为 M ( 1 ≤ M ≤ 1 0 18 ) M(1 \le M \le 10^{18}) M(1≤M≤1018) 。
输入格式
第一行包含两个整数 N N N 和 M M M ，分别是干草包的数量和这顿饭必须有的最小风味之和。
接下来的 N N N 行，每行两个整数描述这 N N N 个草包，首先是风味 F i F_i Fi，然后是辣度 S i S_i Si。
输出格式
请输出这道菜中在满足最低风味时的最低辣度。保证至少有一顿单道菜的饭能满足风味的要求。
题目描述
Farmer John is preparing a delicious meal for his cows! In his barn, he has N N N haybales ( 1 ≤ N ≤ 100 , 000 1 \le N \le 100,000 1≤N≤100,000). The i i ith haybale has a certain flavor F i F_i Fi ( 1 ≤ F i ≤ 1 0 9 1 \le F_i \le 10^9 1≤Fi≤109) and a certain spiciness S i S_i Si ( 1 ≤ S i ≤ 1 0 9 1 \le S_i \le 10^9 1≤Si≤109).
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 M M ( 1 ≤ M ≤ 1 0 18 1 \le M \le 10^{18} 1≤M≤1018).
输入格式
The first line contains the integers N N N and M M M, the number of haybales and the minimum total flavor the meal must have, respectively. The next N N N lines describe the N N N haybales with two integers per line, first the flavor F F F and then the spiciness S S 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
滑动窗口
如果[i…j]的风味足够，则[i…j]一定不劣于a[i…j+1]。
多键有序集合s记录辣度。
代码
核心代码
#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 12 * 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;}inline void write(char ch){*m_p++ = ch;}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);}
private:char puffer[N], * m_p;
};template<int N = 12 * 1'000'000>
class CInBuff
{
public:inline CInBuff() {fread(buffer, 1, N, stdin);}inline int Read() {int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);return f ? -x : x;}
private:char buffer[N], * S = buffer;
};template<class TSave, class TRecord >
class CRangUpdateLineTree
{
protected:virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};template<class TSave, class TRecord >
class CVectorRangeUpdateLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
public:CVectorRangeUpdateLineTree(int iEleSize, TSave tDefault, TRecord tRecordNull) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_record(iEleSize * 4, tRecordNull) {m_recordNull = tRecordNull;}void Update(int iLeftIndex, int iRightIndex, TRecord value){Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);}void Query(int leftIndex, int rightIndex) {Query(1, 0, m_iEleSize - 1, leftIndex, rightIndex);}//void Init() {// Init(1, 0, m_iEleSize - 1);//}TSave QueryAll() {return m_save[1];}void swap(CVectorRangeUpdateLineTree<TSave, TRecord>& other) {m_save.swap(other.m_save);m_record.swap(other.m_record);std::swap(m_recordNull, other.m_recordNull);assert(m_iEleSize == other.m_iEleSize);}
protected://void Init(int iNodeNO, int iSaveLeft, int iSaveRight)//{// if (iSaveLeft == iSaveRight) {// this->OnInit(m_save[iNodeNO], iSaveLeft);// return;// }// const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;// Init(iNodeNO * 2, iSaveLeft, mid);// Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);// this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);//}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {this->OnQuery(m_save[iNodeNO], iSaveLeft, iSaveRight);return;}if (iSaveLeft == iSaveRight) {//没有子节点return;}Fresh(iNodeNO, iSaveLeft, iSaveRight);const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if (mid + 1 <= iQueryRight) {Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value){if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight)){this->OnUpdate(m_save[iNode], iSaveLeft, iSaveRight, value);this->OnUpdateRecord(m_record[iNode], value);return;}if (iSaveLeft == iSaveRight) {return;//没有子节点}Fresh(iNode, iSaveLeft, iSaveRight);const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iMid >= iOpeLeft){Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);}if (iMid + 1 <= iOpeRight){Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);}// 如果有后代，至少两个后代this->OnUpdateParent(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iSaveRight);}void Fresh(int iNode, int iDataLeft, int iDataRight){if (m_recordNull == m_record[iNode]){return;}const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_record[iNode]);Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_record[iNode]);m_record[iNode] = m_recordNull;}vector<TSave> m_save;vector<TRecord> m_record;TRecord m_recordNull;const int m_iEleSize;
};class Solution {
public:int Ans(const long long M, vector<pair<int, int>>& fs) {const int N = fs.size();long long sum = 0;int ans = INT_MAX / 2;multiset<int> s;for (int i = 0, j = 0; i < N; i++) {while ((j < N) && (sum + fs[j].first < M)) {s.emplace(fs[j].second);sum += fs[j].first; j++;}if (j == N) { break; }s.emplace(fs[j].second);sum += fs[j].first; j++;ans = min(ans, *s.rbegin());sum -= fs[i].first;s.erase(s.find(fs[i].second));}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG int n;long long M;cin >> n >> M ;auto a = Read<pair<int,int>>(n); auto res = Solution().Ans(M,a);cout << res;
#ifdef _DEBUG /*printf("T=%d,", T);*/Out(a, "a=");//Out(edge, "edge=");
#endif // DEBUG return 0;
}
单元测试
int M;vector<pair<int, int>>a;TEST_METHOD(TestMethod11){M=10,a = { {4,10},{6,15},{3,5},{4,9},{3,6} };auto res = Solution().Ans(M,a);AssertEx(9, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。