网站防注入怎么办,手机网站开发报价单,网站建设及推广费用怎么入账,如何让百度分享按钮在网站每个页面都有本文涉及知识点
C堆(优先队列)
P9557 [SDCPC 2023] Building Company
题目描述
您是一家建筑公司的老板。一开始#xff0c;公司共有 g g g 类员工#xff0c;每一类员工都属于一个工种。第 i i i 类员工的工种编号为 t i t_i ti#xff0c;共有 u i u_i ui 人。…本文涉及知识点
C堆(优先队列)
P9557 [SDCPC 2023] Building Company
题目描述
您是一家建筑公司的老板。一开始公司共有 g g g 类员工每一类员工都属于一个工种。第 i i i 类员工的工种编号为 t i t_i ti共有 u i u_i ui 人。
市场上共有 n n n 项工程等待承接。想要承接第 i i i 项工程您的公司需要满足 m i m_i mi 项要求其中第 j j j 项要求您的公司至少有工种编号为 a i , j a_{i, j} ai,j 的员工 b i , j b_{i, j} bi,j 人。承接该工程后您的公司将会更加有名并吸引 k i k_i ki 类员工加入公司其中第 j j j 类员工的工种编号为 c i , j c_{i, j} ci,j共有 d i , j d_{i, j} di,j 人。
您可以按任意顺序承接任意数量的工程每项工程最多只能被承接一次。求最多能承接多少工程。
请注意员工不是消耗品。承接一项工程后员工的数量不会减少。
输入格式
每个测试文件仅有一组测试数据。
第一行首先输入一个整数 g g g 1 ≤ g ≤ 10 5 1 \le g \le 10^5 1≤g≤105表示一开始公司内员工的种类数。接下来输入 g g g 对整数 t 1 , u 1 , t 2 , u 2 , ⋯ t g , u g t_1, u_1, t_2, u_2, \cdots t_g, u_g t1,u1,t2,u2,⋯tg,ug 1 ≤ t i , u i ≤ 10 9 1 \le t_i, u_i \le 10^9 1≤ti,ui≤109其中 t i t_i ti 和 u i u_i ui 表示一开始工种编号为 t i t_i ti 的员工共有 u i u_i ui 人。保证对于所有 1 ≤ i j ≤ g 1 \le i j \le g 1≤ij≤g 有 t i ≠ t j t_i \ne t_j titj。
第二行输入一个整数 n n n 1 ≤ n ≤ 10 5 1 \le n \le 10^5 1≤n≤105表示等待承接的工程数量。
对于接下来 2 n 2n 2n 行每两行描述一项工程。
第 ( 2 i − 1 ) (2i - 1) (2i−1) 行首先输入一个整数 m i m_i mi 0 ≤ m i ≤ 10 5 0 \le m_i \le 10^5 0≤mi≤105表示承接第 i i i 项工程有几项要求。接下来输入 m i m_i mi 对整数 a i , 1 , b i , 1 , a i , 2 , b i , 2 , ⋯ , a i , m i , b i , m i a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}, \cdots, a_{i, m_i}, b_{i, m_i} ai,1,bi,1,ai,2,bi,2,⋯,ai,mi,bi,mi 1 ≤ a i , j , b i , j ≤ 10 9 1 \le a_{i, j}, b_{i, j} \le 10^9 1≤ai,j,bi,j≤109其中 a i , j a_{i, j} ai,j 和 b i , j b_{i, j} bi,j 表示公司至少要有工种编号为 a i , j a_{i, j} ai,j 的员工 b i , j b_{i, j} bi,j 人。保证对于所有 1 ≤ x y ≤ m i 1 \le x y \le m_i 1≤xy≤mi 有 a i , x ≠ a i , y a_{i, x} \ne a_{i, y} ai,xai,y。
第 2 i 2i 2i 行首先输入一个整数 k i k_i ki 0 ≤ k i ≤ 10 5 0 \le k_i \le 10^5 0≤ki≤105表示承接第 i i i 项工程之后有几类员工加入公司。接下来输入 k i k_i ki 对整数 c i , 1 , d i , 1 , c i , 2 , d i , 2 , ⋯ , c i , k i , d i , k i c_{i, 1}, d_{i, 1}, c_{i, 2}, d_{i, 2}, \cdots, c_{i, k_i}, d_{i, k_i} ci,1,di,1,ci,2,di,2,⋯,ci,ki,di,ki 1 ≤ c i , j , d i , j ≤ 10 9 1 \le c_{i, j}, d_{i, j} \le 10^9 1≤ci,j,di,j≤109其中 c i , j c_{i, j} ci,j 和 d i , j d_{i, j} di,j 表示工种编号为 c i , j c_{i, j} ci,j 的员工共 d i , j d_{i, j} di,j 人加入公司。保证对于所有 1 ≤ x y ≤ k i 1 \le x y \le k_i 1≤xy≤ki 有 c i , x ≠ c i , y c_{i, x} \ne c_{i, y} ci,xci,y。
保证 m i m_i mi 与 k i k_i ki 之和均不超过 10 5 10^5 105。
输出格式
输出一行一个整数表示最多能承接几项工程。
【样例解释】
样例解释如下用 ( t , u ) (t, u) (t,u) 表示工种为 t t t 的员工有 u u u 名。
首先承接没有任何要求的第 5 5 5 项工程承接后工种为 3 3 3 的 2 2 2 名员工加入公司。公司内现有员工为 { ( 1 , 2 ) , ( 2 , 1 ) , ( 3 , 2 ) } \{(1, 2), (2, 1), (3, 2)\} {(1,2),(2,1),(3,2)}。
接下来承接第 1 1 1 项工程承接后没有员工加入公司。公司内现有员工仍为 { ( 1 , 2 ) , ( 2 , 1 ) , ( 3 , 2 ) } \{(1, 2), (2, 1), (3, 2)\} {(1,2),(2,1),(3,2)}。
接下来承接第 2 2 2 项工程承接后工种为 3 3 3 的 2 2 2 名员工以及工种为 2 2 2 的 1 1 1 名员工加入公司。公司内现有员工为 { ( 1 , 2 ) , ( 2 , 2 ) , ( 3 , 4 ) } \{(1, 2), (2, 2), (3, 4)\} {(1,2),(2,2),(3,4)}。
接下来承接第 4 4 4 项工程承接后工种为 1 1 1 的 3 3 3 名员工加入公司。公司内现有员工为 { ( 1 , 5 ) , ( 2 , 2 ) , ( 3 , 4 ) } \{(1, 5), (2, 2), (3, 4)\} {(1,5),(2,2),(3,4)}。
由于工种为 2 2 2 的员工不足 3 3 3 名因此无法承接仅剩的第 3 3 3 项工程。
输入输出样例 #1
输入 #1
2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2输出 #1
4小根堆
哈希映射int,long long cnt记录第i类员工数量。初始 c n t [ t i ] u i cnt[t_i] u_i cnt[ti]ui 队列que 记录将获得员工种类和数量。 对所有初始符合条件的项目i, a i , j , b i , j 入队 a_{i,j},b_{i,j}入队 ai,j,bi,j入队 对所有初始不符合条件的项目i第j中员不组则 n e e d P o p [ c i , j ] . e m p l a c e ( d i , j , i ) needPop[c_{i,j}].emplace(d_{i,j},i) needPop[ci,j].emplace(di,j,i) needPop是哈希映射int,小跟堆 同时needPro[i]。 处理队首{kind,c}直到空 cnt[kind] c 当 cnt[kind] needPop[kind].top().first { needPor[needPop[kind].top().second]– 如果needPop[kind].top() 等于0needPop[kind].top()获得的员工入队。 出堆 } 入队最多 ∑ k i \sum k_i ∑ki此入堆最多 ∑ m i \sum m_i ∑mi次故时间复杂度**O(1e5log1e5)
代码
核心代码
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist
#includearray#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T1, class T2, class T3, class T4, class T5, class T6, class T7
std::istream operator (std::istream in, tupleT1, T2, T3, T4,T5,T6,T7 t) {in get0(t) get1(t) get2(t) get3(t) get4(t) get5(t) get6(t);return in;
}templateclass T int
vectorT Read() {int n;cin n;vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}
templateclass T int
vectorT ReadNotNum() {vectorT ret;T tmp;while (cin tmp) {ret.emplace_back(tmp);if (\n cin.get()) { break; }}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 1000000
class CInBuff
{
public:inline CInBuff() {}inline CInBuffN operator(char ch) {FileToBuf();while ((\r *S) || (\n *S) || ( *S)) { S; }//忽略空格和回车ch *S;return *this;}inline CInBuffN 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;}templateclass T1, class T2inline CInBuff operator(pairT1, T2 val) {*this val.first val.second;return *this;}templateclass T1, class T2, class T3inline CInBuff operator(tupleT1, T2, T3 val) {*this get0(val) get1(val) get2(val);return *this;}templateclass T1, class T2, class T3, class T4inline CInBuff operator(tupleT1, T2, T3, T4 val) {*this get0(val) get1(val) get2(val) get3(val);return *this;}templateclass T intinline CInBuff operator(vectorT val) {int n;*this n;val.resize(n);for (int i 0; i n; i) {*this val[i];}return *this;}templateclass T intvectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {*this ret[i];}return ret;}templateclass T intvectorT Read() {vectorT 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(vectorpairint, int tu, vectorvectorpairint, int ab, vectorvectorpairint, int cd) {const int N ab.size();unordered_mapint, long long cnt;unordered_mapint, priority_queuepairint, int, vectorpairint, int, greater needPop;vectorint proNeed(N);queuepairint, long long que;auto Finish [](int iPro) {if (0 ! proNeed[iPro]) { return; }for (const auto [t, u] : cd[iPro]) {que.emplace(t, u);}};for (const auto [t, u] : tu) {cnt[t] u;}for (int i 0; i N; i) {for (const auto [t, u] : ab[i]) {if (cnt[t] u) {needPop[t].emplace(u, i);proNeed[i];}}Finish(i);}while (que.size()) {const auto [t, u] que.front(); que.pop();cnt[t] u;while (needPop[t].size() (needPop[t].top().first cnt[t])) {proNeed[needPop[t].top().second]--;Finish(needPop[t].top().second);needPop[t].pop();}}return std::count(proNeed.begin(), proNeed.end(), 0);}
};int main() {
#ifdef _DEBUGfreopen(a.in, r, stdin);
#endif // DEBUG ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff in; COutBuff10000000 ob;int N 0;auto tu Readpairint, int();cin N;vectorvectorpairint,int ab(N), cd(N);for (int i 0; i N; i){ab[i] Readpairint, int();cd[i] Readpairint, int();}auto res Solution().Ans(tu,ab,cd);
#ifdef _DEBUG //printf(N%lld,K%d,M%d,a%d,b%d, N, K,M,a,b);Out(tu, ,tu);Out(ab, ,ab);Out(cd, ,cd);
#endif // DEBUG cout res \n;return 0;
};单元测试
vectorpairint, int tu;vectorvectorpairint, int ab, cd;TEST_METHOD(TestMethod11){tu { {2,1},{1,2} }, ab { {{3,1}},{{1,1},{2,1}},{{1,5},{2,3},{3,4}},{{2,1},{1,1},{3,
4}},{} }, cd { {},{{3,2},{2,1}},{{2,5}},{{1,3}},{{3,2}} };auto res Solution().Ans(tu,ab,cd);AssertEx(4, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
