蓝桥杯 第十二届国赛真题-巧克力优先队列 + 贪心
链接:第十二届国赛真题-巧克力
题意:
思路:
- 第一眼看上去就像贪心,但具体不知道怎么贪,优先选便宜的,或者优先选保质期短的貌似都不行。
- 仔细想了想 ,因为我们优先选便宜的可能会导致,让这个巧克力在后面选,且让和它价格差不多的巧克力先选可能更优,所以我们不妨从最后一天开始考虑,把符合要求的巧克力都加入备选集合,然后选择价格最便宜的巧克力,用优先队列维护即可。
代码:
#include<bits/stdc .h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const ll de = 4e10;
const int maxn = 2e6 7;
int x , n;
ll ans;
struct node{
int a , b , c;
friend bool operator < (node A, node B){
return A.a > B.a;
}
}num[maxn];
bool cmp(node A , node B){
return A.b < B.b;
}
priority_queue<node> que;
int main(){
scanf("%d%d",&x,&n);
for(int i = 1; i <= n; i ){
scanf("%d%d%d",&num[i].a,&num[i].b,&num[i].c);
}
sort(num 1,num n 1 , cmp);
int pos = n;
for(int i = x; i >= 1; i --){
while(num[pos].b >= i){
que.push(num[pos]);
pos--;
}
if(que.size() == 0){
ans = -1;
break;
}
node now = que.top();
que.pop();
ans = now.a;
now.c --;
if(now.c) que.push(now);
}
printf ("%lld\n",ans);
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehgcf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01