华为

发布时间：2025-09-01 06:43

https://oj.algomooc.com/problem.php?id=3131
歌手准备从A" role="presentation">A城去B" role="presentation">B城参加演出

按照合同，他必须在T" role="presentation">T天内赶到。歌手途径N" role="presentation">N座城市。歌手不能往回走。每两座城市之间需要的天数都可以提前获知。歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期。如果在一座城市第一天卖唱可以赚M" role="presentation">M，后续每天的收入会减少D" role="presentation">D(第二天赚的钱是M−D" role="presentation">M−D，第三天是M−2D" role="presentation">M−2D…)。如果收入减到0" role="presentation">0就不会再少了。歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。问贪心的歌手最多可以赚多少钱?

输入
第一行两个数字 T 和 N，中间用空格隔开，T 代表总天数；
N 代表路上经过 N 座城市;
0 < T < 1000，0 < N < 100
第二行 N+1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和<=T。
接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期。
0 < M < 1000，0 < D < 100

输出
一个数字。代表歌手最多可以赚多少钱。以回车结束

示例一
输入
10 2
1 1 2
120 20
90 10
复制
输出
540
复制
说明
总共 10 天，路上经过 2 座城市。路上共花 1+1+2=4 天。剩余 6 天最好的计划是在第一座城市待 3 天，在第二座城市待 3 天。在第一座城市赚的钱：120 + 100 + 80 = 300 在第二座城市赚的钱：90 + 80 + 70 = 240
共 300 +240 = 540

样例输入复制
10 3
1 1 2 3
120 20
90 10
100 20
样例输出复制
320

题目解析

首先歌手能够卖唱的所有天数是固定的。假设总时间为T" role="presentation">T，花费在路上的时间数组为days" role="presentation">days，那么可以停下来卖唱的时间为X=T−sum(days)" role="presentation">X=T−sum(days)。这是很容易分析出来的结论。
那么为了能够赚更多的钱，我们一定要把X天都拉满，即尽可能地停留在某个城市赚钱。
这X" role="presentation">X天的分配实际上是任意的，停留在哪一个城市都行，只要停留够X" role="presentation">X天就肯定能赚到尽可能多的钱。实际上我们并不需要按照歌手的时间线来考虑问题，而是按照某一天能够在哪个城市获得的钱数最多来考虑问题的。
考虑例子2：
停留的卖唱天数X = (10-1-1-2-3)=3，第一个城市的起始金额M1 = 120，衰减速度D1 = 20，第二个城市的起始金额M2 = 100，衰减速度D2 = 10,第三个城市的起始金额M3 = 100，衰减速度D2 = 20。我们会做如下分析：
所以我们分析一下就是:ans=120+100+100,第二个100，是第一个城市衰减了一次
虽然真正的时间线为1(两天) -> 2->3(一天)。
上述过程涉及到动态维护最大值的情形，很显然可以使用优先队列来维护该过程。具体过程如下：
构建一个以最大值为排序依据的优先队列（即大根堆）heap
将每一个城市的(M, D)储存在堆中。
循环X次，表示最多可以停留X天在进行卖唱。
弹出堆顶元素M, D，此时可以赚到M，即更新ans += M
计算衰减后该城市能够赚到的钱M -= D。
如果M衰减了D之后，仍大于0，说明还有可能继续在这个城市赚钱，需要将(M, D)重新入堆
注意在循环中，必须判断heap的长度是否大于0。如果等于0，说明优先队列中无元素，所有的城市赚的钱都衰减到0了，此时可以直接退出循环。

所以这个题就是优先队列就行.

#include<iostream> #include<algorithm> #include<queue> using namespace std; int main(){int t,n;cin>>t>>n;for(int i=1;i<=n+1;i++){int x;cin>>x;t-=x;}priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>>q;for(int i=1;i<=n;i++){int M, D; cin >> M >> D;q.push({M,D});}int ans=0;while(t--&&q.size()){int M=q.top().first;int D=q.top().second;q.pop();ans+=M;if((M-D)>0)q.push({M-D,D});}cout<<ans<<endl; }

网址：华为 https://m.mxgxt.com/news/view/1738064

⬅️上一篇：小明星（其他人物相关）

➡️下一篇：香港歌手何雁诗自杀原因是什么回

华为

题目解析

相关内容

随便看看

最新实时动态

热点实时动态

专题

推荐实时动态