![打卡信奥刷题（3020）用C++实现信奥题 P6359 [CEOI 2018] Cloud computing](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3020）用C++实现信奥题 P6359 [CEOI 2018] Cloud computing)
P6359 [CEOI 2018] Cloud computing题目背景译自 CEOI2018 Day1 T1. Cloud Computing。题目描述Johnny 创立了 Bytecomp一家提供云计算能力的公司。这样的公司通常拥有许多快速的计算机可以让客户在上面进行计算。Johnny 仍然没有购买任何机器。他去了一家计算机商店收到了一个包含所有n nn台可用的计算机的清单。每台计算机都可以用三个属性描述处理器内核数c i c_ici时钟频率f i f_ifi和价格v i v_ivi。这样的计算机包含c i c_ici个独立的内核所以他们可以被分配不同的任务。当客户订购资源时她会指定所需的内核数C j C_jCj和最小的时钟频率F j F_jFj。订单还包含客户愿意支付的价格V j V_jVj。如果接受订单Bytecomp 需要提供客户所需计算能力的独占访问权。Johnny 需要选择C j C_jCj个核心可能来自不同的计算机且它们的时钟频率至少为F j F_jFj这些核心不能被分配给其它订单。帮助 Johnny 赚尽可能多的钱接受一个最优的订单子集选择所有计算机的一个子集来满足所有接受了的订单。你的目标是最大化利润即为客户提供计算能力的收入与购买计算机的成本之差。输入格式标准输入的第一行包含一个整数n nn表示商店中可用计算机的数量。接下来n nn行每行描述一台计算机包含三个空格隔开的整数c i , f i , v i c_i, f_i, v_ici,fi,vi分别表示内核数时钟频率和价格。接下来一行一个整数m mm表示客户的订单数量。接下来m mm行每行描述一个订单包含三个空格隔开的整数C j , F j , V j C_j, F_j, V_jCj,Fj,Vj分别表示需要的核心数最低的允许的时钟频率以及预算。输出格式标准输出唯一的一行包含一个整数表示能够得到的最大利润。输入输出样例 #1输入 #14 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550输出 #1350说明/提示样例解释一共有四台可用的计算机和三个订单。最佳方案是购买两台价格为700 700700和750 750750总计1450 14501450的四内核的计算机然后接受前两个订单获得300 1500 1800 3001500180030015001800的收益。我们获得了四个时钟频率为2000 20002000的内核和四个时钟频率为2200 22002200的内核。可以将其中六个分配给第二个订单需要1900 19001900的时钟频率再将其中一个分配给第一个订单需要1500 15001500的时钟频率剩下一个核心不使用这是允许的。总利润为1800 − 1450 350 1800-14503501800−1450350。数据规模与约定对于100 % 100\%100%的数据1 ≤ n , m ≤ 2 × 10 3 , 1 ≤ c i , C i ≤ 50 , 1 ≤ f i , F i , v i , V i ≤ 10 9 1\le n,m\le 2\times 10^3,\ 1\le c_i,C_i\le 50,\ 1\le f_i,F_i,v_i,V_i\le 10^91≤n,m≤2×103,1≤ci,Ci≤50,1≤fi,Fi,vi,Vi≤109。所有测试数据被划分成若干个有附加限制的子任务每个子任务中包含若干测试点。子任务附加限制分值1 11n ≤ 15 n \le 15n≤1518 18182 22m ≤ 15 m \le 15m≤1518 18183 33n , m ≤ 100 n,m \le 100n,m≤100c i C j 1 c_i C_j 1ciCj118 18184 44f i F j 1 f_i F_j 1fiFj118 18185 55v i V j 1 v_i V_j 1viVj118 18186 66无附加限制10 1010C实现#includebits/stdc.husingnamespacestd;usinglllonglong;//不开long long见祖宗constll N2e510;ll n,m,ct,ans,dp[N];structPc{ll c,f,v;}s[N];boolcmp(Pc l,Pc r){if(l.fr.f)returnl.vr.v;returnl.fr.f;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cins[i].cs[i].fs[i].v;s[i].v-s[i].v;//为了区分购进的电脑和订单电脑的价格用负数存}cinm;for(intin1;inm;i)cins[i].cs[i].fs[i].v;sort(s1,snm1,cmp);memset(dp,128,sizeof(dp));dp[0]0;for(inti1;inm;i){//01背包if(s[i].v0){for(intjct;j0;j--)dp[js[i].c]max(dp[js[i].c],dp[j]s[i].v);cts[i].c;//ct记录当前的核心数确定dp的范围}else{for(intj0;jct-s[i].c;j)dp[j]max(dp[j],dp[js[i].c]s[i].v);}}for(intj0;jct;j)ansmax(ans,dp[j]);coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3020）用C++实现信奥题 P6359 [CEOI 2018] Cloud computing
发布时间：2026/5/20 12:03:34
P6359 [CEOI 2018] Cloud computing题目背景译自 CEOI2018 Day1 T1. Cloud Computing。题目描述Johnny 创立了 Bytecomp一家提供云计算能力的公司。这样的公司通常拥有许多快速的计算机可以让客户在上面进行计算。Johnny 仍然没有购买任何机器。他去了一家计算机商店收到了一个包含所有n nn台可用的计算机的清单。每台计算机都可以用三个属性描述处理器内核数c i c_ici时钟频率f i f_ifi和价格v i v_ivi。这样的计算机包含c i c_ici个独立的内核所以他们可以被分配不同的任务。当客户订购资源时她会指定所需的内核数C j C_jCj和最小的时钟频率F j F_jFj。订单还包含客户愿意支付的价格V j V_jVj。如果接受订单Bytecomp 需要提供客户所需计算能力的独占访问权。Johnny 需要选择C j C_jCj个核心可能来自不同的计算机且它们的时钟频率至少为F j F_jFj这些核心不能被分配给其它订单。帮助 Johnny 赚尽可能多的钱接受一个最优的订单子集选择所有计算机的一个子集来满足所有接受了的订单。你的目标是最大化利润即为客户提供计算能力的收入与购买计算机的成本之差。输入格式标准输入的第一行包含一个整数n nn表示商店中可用计算机的数量。接下来n nn行每行描述一台计算机包含三个空格隔开的整数c i , f i , v i c_i, f_i, v_ici,fi,vi分别表示内核数时钟频率和价格。接下来一行一个整数m mm表示客户的订单数量。接下来m mm行每行描述一个订单包含三个空格隔开的整数C j , F j , V j C_j, F_j, V_jCj,Fj,Vj分别表示需要的核心数最低的允许的时钟频率以及预算。输出格式标准输出唯一的一行包含一个整数表示能够得到的最大利润。输入输出样例 #1输入 #14 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550输出 #1350说明/提示样例解释一共有四台可用的计算机和三个订单。最佳方案是购买两台价格为700 700700和750 750750总计1450 14501450的四内核的计算机然后接受前两个订单获得300 1500 1800 3001500180030015001800的收益。我们获得了四个时钟频率为2000 20002000的内核和四个时钟频率为2200 22002200的内核。可以将其中六个分配给第二个订单需要1900 19001900的时钟频率再将其中一个分配给第一个订单需要1500 15001500的时钟频率剩下一个核心不使用这是允许的。总利润为1800 − 1450 350 1800-14503501800−1450350。数据规模与约定对于100 % 100\%100%的数据1 ≤ n , m ≤ 2 × 10 3 , 1 ≤ c i , C i ≤ 50 , 1 ≤ f i , F i , v i , V i ≤ 10 9 1\le n,m\le 2\times 10^3,\ 1\le c_i,C_i\le 50,\ 1\le f_i,F_i,v_i,V_i\le 10^91≤n,m≤2×103,1≤ci,Ci≤50,1≤fi,Fi,vi,Vi≤109。所有测试数据被划分成若干个有附加限制的子任务每个子任务中包含若干测试点。子任务附加限制分值1 11n ≤ 15 n \le 15n≤1518 18182 22m ≤ 15 m \le 15m≤1518 18183 33n , m ≤ 100 n,m \le 100n,m≤100c i C j 1 c_i C_j 1ciCj118 18184 44f i F j 1 f_i F_j 1fiFj118 18185 55v i V j 1 v_i V_j 1viVj118 18186 66无附加限制10 1010C实现#includebits/stdc.husingnamespacestd;usinglllonglong;//不开long long见祖宗constll N2e510;ll n,m,ct,ans,dp[N];structPc{ll c,f,v;}s[N];boolcmp(Pc l,Pc r){if(l.fr.f)returnl.vr.v;returnl.fr.f;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cins[i].cs[i].fs[i].v;s[i].v-s[i].v;//为了区分购进的电脑和订单电脑的价格用负数存}cinm;for(intin1;inm;i)cins[i].cs[i].fs[i].v;sort(s1,snm1,cmp);memset(dp,128,sizeof(dp));dp[0]0;for(inti1;inm;i){//01背包if(s[i].v0){for(intjct;j0;j--)dp[js[i].c]max(dp[js[i].c],dp[j]s[i].v);cts[i].c;//ct记录当前的核心数确定dp的范围}else{for(intj0;jct-s[i].c;j)dp[j]max(dp[j],dp[js[i].c]s[i].v);}}for(intj0;jct;j)ansmax(ans,dp[j]);coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
