当前位置：首页 > java >正文

【贪心单调栈】P10334 [UESTCPC 2024] 饮料|普及+

java 2025/8/29 7:28:15

本文涉及知识点

C++贪心
C++单调栈

P10334 [UESTCPC 2024] 饮料

题目描述

有一个果汁机，每分钟可以制作一杯任意体积的果汁。

有 $n$ 个人排成一队。第 $i$ 个人将在第 $t_i$ 分钟走到果汁机前，并拿走当前已经制作的果汁中体积最大的一杯。第 $i$ 个人拿到体积大于等于 $a_i$ 的果汁就会满意。如果此时没有果汁，则第 $i$ 个人也会不满意。

问是否能够让所有人满意。如果是，输出让所有人满意所需的果汁体积之和的最小值。

输入格式

第一行一个整数 $n$ $(1≤n≤2×105)(1\leq n\leq 2 \times 10^5)$ ，表示队伍中人的数量。

接下来一行 $n$ 个整数 $t1,t2,…,tnt_1,t_2,\ldots,t_n$ $(1≤t1≤t2≤…≤tn≤109)(1\leq t_1\leq t_2\leq\ldots\leq t_n\leq 10^9)$ ，其中 $t_i$ 表示第 $i$ 个人到果汁机前的时间。如果两个人的到达时间相同，则按题目给出的顺序从左到右决定先后。

接下来一行 $n$ 个整数 $a1,a2,…,ana_1,a_2,\ldots,a_n$ $(1≤ai≤109)(1\leq a_i\leq 10^9)$ ，其中 $a_i$ 表示第 $i$ 个人对果汁的体积要求。

输出格式

如果不能令所有人满意，输出 $- 1$ 。

否则输出一行一个整数，表示所需的最小体积和。

输入输出样例 #1

输入 #1

5
1 3 4 6 6
3 8 2 7 4

输出 #1

输入输出样例 #2

输入 #2

5
1 3 4 5 5
3 8 2 7 4

输出 #2

说明/提示

样例一解释如下：

时间	制作	取走
$1$	$3$	$3$
$2$	$-$	$-$
$3$	$8$	$8$
$4$	$2$	$2$
$5$	$4$	$-$
$6$	$7$	$7, 4$

样例二解释如下：

时间	制作	取走
$1$	$3$	$3$
$2$	$4$	$-$
$3$	$8$	$8$
$4$	$4$	$4$
$5$	$7$	$7, 4$
$6$	$-$	$-$

贪心（错误）

性质一：每杯果汁都尽可能晚制作。

实现

按取果汁的时间逆序求做果汁的时间。如果时间相等，先做体积小的。
由于t最大1e9，故不能枚举空闲时间。记录做果汁的连续区间。
如果最后一个区间不包括t，则在t时间做。
否则在最后一个区间的前1秒做，如果最后一个区间已经从1开始，则返回-1。注意：倒数第二个区间和第一个区间合并。
多键有序集合记录已经做了未取的果汁，按取果汁顺序取，如果最大值不是当前要取的果汁。则只能将当前果汁换成最大值。
时间复杂度：O(nlogn)

错误原因

第二、四、四取体积1的果汁，第三分钟取题解4的果汁。
题解的做法：第1到4分钟，分别做{1,4,1,1}。
正确做法：{1,1,4,1}

贪心

性质一：体积最大的果汁如果在第t分钟取，则一定在做。否则交换之。
性质二：按体积降序处理，在t1时间做， $\in[1,t],t1空闲，且最大$
通过不了，记录操作记录逆推演算，结果不对。
第二分钟：9，第三分钟8，第5分钟3杯10。
按题解：9，10（8改),10,10,10
正确全部10
可以继续尝试，比如线段树，我选择了查看正解。

代码

核心代码

#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<array>#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, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6, T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(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();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车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:long long Ans(const vector<int>& ts,const vector<int>& as) {	const int N = ts.size();vector<int> tDebug(N),aDebug(N);//何时给第i个人做，及体积vector<int> inxs(N);iota(inxs.begin(), inxs.end(), 0);sort(inxs.begin(), inxs.end(), [&](int i1, int i2) {return as[i1] > as[i2]; });vector<pair<int, int>> ta;map<int, int> beginEnd = { { 0,0 }, { INT_MAX / 2,INT_MAX / 2} };auto Add = [&](int left){	int r = left;auto it = beginEnd.upper_bound(left);auto it1 = prev(it);if (it->first == r + 1) {r = it->second;beginEnd.erase(it);}if (it1->second + 1 == left) {left = it1->first;beginEnd.erase(it1);}beginEnd.emplace(left, r);};for (int i :inxs) {	auto it = beginEnd.lower_bound(ts[i]);int t = -1;if (it->first == ts[i]) {t = ts[i] - 1;}else {auto it1 = prev(it);if (it1->second >= ts[i]) {t = it1->first - 1;}else {t = ts[i];}} if (t < 1) { return -1; }Add(t);ta.emplace_back(t, as[i]);tDebug[i] = t;}sort(ta.begin(), ta.end(),greater<>());multiset<int> has;long long ans = 0;for (int i = 0; i < N; i++) {while (ta.size() && (ta.back().first <= ts[i])) {has.emplace(ta.back().second);ta.pop_back();}aDebug[i] = *has.rbegin();ans += *has.rbegin();has.erase(has.find(as[i]));}Check(ts, tDebug, aDebug);return ans;}void Check(const vector<int>& ts, const vector<int>& tDebug,const vector<int>& aDebug) {const int N = ts.size();multiset<int> has;unordered_set<int> tmp;tmp.insert(tDebug.begin(), tDebug.end());assert(tDebug.size() == tmp.size());const int iMin = *min_element(tDebug.begin(), tDebug.end());assert(iMin > 0);vector<int> inxDebug(N);iota(inxDebug.begin(), inxDebug.end(), 0);sort(inxDebug.begin(), inxDebug.end(), [&](int i1, int i2) {return tDebug[i1] > tDebug[i2]; });for (int i = 0; i < N; i++) {while (inxDebug.size() && (tDebug[inxDebug.back()] <= ts[i])) {has.emplace(aDebug[inxDebug.back()]);inxDebug.pop_back();}assert(aDebug[i] == *has.rbegin());has.erase(has.find(aDebug[i]));}}};
int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int N;cin >> N;auto ts = Read<int>(N);auto as = Read<int>(N);
#ifdef _DEBUG	//printf("N=%d", N);Out(as, ",as=");//Out(P, ",P=");Out(ts, ",ts=");//Out(que, ",ope=");
#endif // DEBUG		auto res = Solution().Ans(ts,as);cout << res << "\n";
}

单调栈

性质一：本题按ts序取饮料。故 $∀i∈[0,N−1]\forall i \in[0,N-1]$ ,最多做ts[i]杯果汁，已经取走i杯。故 $\ge i+1$ 一定有解，否则无解。
单调栈need记录比第i杯果汁晚取，且没有做的果汁。i = N-1 to 0
细节一：将a[i]放到need中前：
need中的果汁符合以下两个条件：
a,取的时候晚于果汁i。
b，取a[i]时，果汁没有制作。
即：在取a[i]之前制作，且在取a[i]时，没取走。
即：如果 $a [i] < ma x (n ee d)$ 会取走max(need)，故max(a[i],max(need))入栈。
即单调栈从栈底到栈顶升序。
性质二：走开右闭空间(ts[i],ts[i+1])共can = ts[i+1]-ts[i]分钟。可以做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<array>#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, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6, T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(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();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车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:long long Ans(const vector<int>& ts,const vector<int>& as) {	const int N = ts.size();for (int i = 0; i < N; i++) {if (ts[i] < i + 1) { return -1; }}long long ans = 0;stack<int> need;for (int i = N - 1; i >= 0; i--) {int can = (i + 1 == N) ? 0 : (ts[i + 1] - ts[i]);can = min((int)need.size(), can);while (can) {ans += need.top();need.pop(); can--;}if (need.size()) {need.emplace(max(need.top(), as[i]));}else {need.emplace(as[i]);}}while (need.size()) {ans += need.top(); need.pop();}return ans;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int N;cin >> N;auto ts = Read<int>(N);auto as = Read<int>(N);
#ifdef _DEBUG	//printf("N=%d", N);Out(as, ",as=");//Out(P, ",P=");Out(ts, ",ts=");//Out(que, ",ope=");
#endif // DEBUG		auto res = Solution().Ans(ts,as);cout << res << "\n";
}

单元测试

vector<int> ts,as;TEST_METHOD(TestMethod11){as = { 3,8,2,7,4 }, ts = { 1,3,4,6,6 };auto res = Solution().Ans(ts,as);AssertEx(24LL, res);}TEST_METHOD(TestMethod12){as = { 3,8,2,7,4 }, ts = { 1,3,4,5,5 };auto res = Solution().Ans(ts, as);AssertEx(26LL, res);}TEST_METHOD(TestMethod13){as = { 1,4,1,1 }, ts = { 2,3,4,4 };auto res = Solution().Ans(ts, as);AssertEx(7LL, res);}TEST_METHOD(TestMethod14){as = { 9,8,10,10,10 }, ts = { 2,3,5,5,5 };auto res = Solution().Ans(ts, as);AssertEx(50LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功