【区间贪心】P1607 [USACO09FEB] Fair Shuttle G|省选-
尽管农夫约翰在集市上四处走动以收集奖品或观看表演没有问题，但他的奶牛们却没有那么好的体力；在集市上走一天会让它们筋疲力尽。为了让它们享受集市，FJ 安排了一辆穿梭卡车在集市场地内接送奶牛。FJ 无法租到一辆非常好的穿梭车，所以他租的穿梭车只沿着它的路线行驶一次，并在路径上停靠 $N$（$1\leq N\leq2\times10^4$）个站点（编号为 $1\dots N$）。总共有 $K$（$1\l
本文涉及知识点
区间贪心：最多不相交区间、区间选点、区间合并、区间覆盖、区间分组
P1607 [USACO09FEB] Fair Shuttle G
题目描述
尽管农夫约翰在集市上四处走动以收集奖品或观看表演没有问题，但他的奶牛们却没有那么好的体力；在集市上走一天会让它们筋疲力尽。为了让它们享受集市，FJ 安排了一辆穿梭卡车在集市场地内接送奶牛。
FJ 无法租到一辆非常好的穿梭车，所以他租的穿梭车只沿着它的路线行驶一次，并在路径上停靠 N N N（ 1 ≤ N ≤ 2 × 1 0 4 1\leq N\leq2\times10^4 1≤N≤2×104）个站点（编号为 1 … N 1\dots N 1…N）。总共有 K K K（ 1 ≤ K ≤ 5 × 1 0 4 1\leq K\leq5\times10^4 1≤K≤5×104）组奶牛（编号为 1 … K 1\dots K 1…K）希望使用穿梭车，每组 i i i 中的 M i M_i Mi（ 1 ≤ M i ≤ N 1\leq M_i\leq N 1≤Mi≤N）头奶牛希望从一个站点 S i S_i Si（ 1 ≤ S i < E i 1\leq S_i<E_i 1≤Si<Ei）乘车到沿路线更远的另一个站点 E i E_i Ei（ S i < E i ≤ N S_i<E_i\leq N Si<Ei≤N）。
穿梭车可能无法接载整组奶牛（因为它的容量有限），但可以根据需要接载部分奶牛。
给定穿梭卡车的容量 C C C（ 1 ≤ C ≤ 100 1\leq C\leq100 1≤C≤100）以及希望参观集市上各个地点的奶牛组的描述，确定在集市期间可以乘坐穿梭车的奶牛的最大数量。
输入格式
第一行：包括三个整数： K , N K,N K,N 和 C C C，彼此用空格隔开。
第二行到 K + 1 K+1 K+1 行：在第 i + 1 i+1 i+1 行，将会告诉你第 i i i 组奶牛的信息： S i , E i S_i,E_i Si,Ei 和 M i M_i Mi，彼此用空格隔开。
输出格式
第一行：可以坐班车的奶牛的最大头数。
输入输出样例 #1
输入 #1
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
输出 #1
10
说明/提示
【样例说明】
班车可以把 2 2 2 头奶牛从 1 1 1 送到 5 5 5， 3 3 3 头奶牛从 5 5 5 送到 8 8 8， 2 2 2 头奶牛从 8 8 8 送到 14 14 14， 1 1 1 头奶牛从 9 9 9 送到 12 12 12， 1 1 1 头奶牛从 13 13 13 送到 14 14 14， 1 1 1 头奶牛从 14 14 14 送到 15 15 15。
（由 ChatGPT 4o 翻译）
区间
典型的选择N组区间。和经典样例有两点不同：
一， e i ≤ s j e_i \le s_j ei≤sj，本题是 ≤ \le ≤，经典样例是<。
二，本题任何区间有多个，故需要用有序映射代替有序集合记录区间最大端点。
增加元素最多M次。
groupEnd[e] += (mHas - m);
故goupEnd的元素数量不超过M+1次，故删除次数不超过M。
it = groupEnd.erase(it);
以下代码也最多执行M次，每个区间最多执行一次。
it->second -= can;
代码
核心代码
#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 T1, class T2, class T3, class T4, class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
return in;
}
template<class T1, class T2, class T3, class T4, class T5, class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t);
return in;
}
template<class T = int>
vector<T> Read() {
int n;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\n' == cin.get()) { break; }
}
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 = 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;
AuotToFile();
}
void writestr(const char* sz) {
strcpy(m_p, sz);
m_p += strlen(sz);
AuotToFile();
}
inline void write(char ch)
{
*m_p++ = ch;
AuotToFile();
}
inline void ToFile() {
fwrite(puffer, 1, m_p - puffer, stdout);
m_p = puffer;
}
~COutBuff() {
ToFile();
}
private:
inline void AuotToFile() {
if (m_p - puffer > N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};
template<int N = 1'000'000>
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff<N>& operator>>(char& ch) {
FileToBuf();
ch = *S++;
return *this;
}
inline CInBuff<N>& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
template<class T1, class T2>
inline CInBuff& operator>>(pair<T1, T2>& val) {
*this >> val.first >> val.second;
return *this;
}
template<class T1, class T2, class T3>
inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return *this;
}
template<class T1, class T2, class T3, class T4>
inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return *this;
}
template<class T = int>
inline CInBuff& operator>>(vector<T>& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
*this >> val[i];
}
return *this;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
*this >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> Read() {
vector<T> ret;
*this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};
class Solution {
public:
int Ans(const int N, const int C, const vector<tuple<int, int, int>> sem) {
vector<tuple<int, int, int >> esm;
for (const auto& [s, e, m] : sem) {
esm.emplace_back(e, s, m);
}
sort(esm.begin(), esm.end());
map<int, int> groupEnd;
int ans = 0, c = 0;
for (auto [e, s, mHas] : esm) {
auto m = mHas;
auto it = groupEnd.upper_bound(s);
while ((groupEnd.begin() != it) && m) {
--it;
const int can = min(it->second, m);
m -= can;
if (can < it->second) {
it->second -= can;
}
else {
it = groupEnd.erase(it);
}
}
if (m) {
const int can = min(m, C - c);
c += can;
m -= can;
}
ans += (mHas - m);
groupEnd[e] += (mHas - m);
}
return ans;
}
};
int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
ios::sync_with_stdio(0); cin.tie(nullptr);
int K,N, C;
cin >> K >> N >> C;
auto sem = Read < tuple<int, int, int>>(K);
#ifdef _DEBUG
printf("N=%d,C=%d,", N,C);
Out(sem, "sem=");
//Out(edge2, ",edge2=");
//Out(B, "B=");
//Out(que, "que=");
//Out(B, "B=");
#endif // DEBUG
auto res = Solution().Ans(N,C,sem);
cout << res;
return 0;
};
单元测试
int N, C;
vector<tuple<int, int, int>> sem;
TEST_METHOD(TestMethod01)
{
N = 15, C = 3, sem = { {1,5,2},{13,14,1},{5,8,3},{8,14,2},{14,15,1},{9,12,1},{12,15,2},{4,6,1} };
auto res = Solution().Ans(N,C,sem);
AssertEx(10, res);
}
TEST_METHOD(TestMethod02)
{
N = 20, C = 2, sem = { {1,2,1},{1,4,1},{3,7,1},{5,6,1} };
auto res = Solution().Ans(N, C, sem);
AssertEx(4, res);
}
细节优化
class Solution {
public:
int Ans(const int N, const int C, const vector<tuple<int, int, int>> sem) {
vector<tuple<int, int, int >> esm;
for (const auto& [s, e, m] : sem) {
esm.emplace_back(e, s, m);
}
sort(esm.begin(), esm.end());
map<int,int> groupEnd;
groupEnd[-1] = C;
int ans = 0;
for (auto [e, s, mHas] : esm) {
auto m = mHas;
auto it = groupEnd.upper_bound(s);
while ((groupEnd.begin() != it) && m) {
--it;
const int can = min(it->second, m);
m -= can;
if (can < it->second) {
it->second -= can;
}
else {
it = groupEnd.erase(it);
}
}
ans += (mHas - m);
groupEnd[e] += (mHas - m);
}
return ans;
}
};
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步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++**实现。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
16
0- 0
已为社区贡献22条内容
所有评论(0)