首页 > 其他分享 >acw 145. 超市

acw 145. 超市

时间:2022-12-02 18:22:33浏览次数:45  
标签:cnt 145 int top 超市 tm acw

超市里有n件商品,每件商品都有利润v[i] 和过期时间tm[i] ,

每天只能卖一件商品,过期商品不能卖。

求可以得到的最大收益

 

#include "bits/stdc++.h"
using namespace std;
 const int N=1e5+5;
 struct T{
     int v,tm;
 }a[N];
 int n;
 bool cmp(T &A,T &B){
     if(A.tm==B.tm) return A.v>B.v;
     return A.tm<B.tm;
 }
 void sov(){
     int i,t;
   priority_queue<int,vector<int>,greater<int> > q;
   for(i=1;i<=n;i++) cin>>a[i].v>>a[i].tm;
   sort(a+1,a+1+n,cmp);
   t=0;
   int cnt=0;
   for(i=1;i<=n;i++){
        if(a[i].tm>cnt) cnt++,t+=a[i].v,q.push(a[i].v);
        else if(a[i].v>q.top())
         t-=q.top(),t+=a[i].v,q.pop(),q.push(a[i].v); 
   }
   cout<<t<<endl;
 }
 main(){
     while(cin>>n) sov();
 }

 

标签:cnt,145,int,top,超市,tm,acw
From: https://www.cnblogs.com/towboa/p/16945292.html

相关文章

  • 时间 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • acwing 140. 后缀数组
    把字符串S的所有后缀按照字典序排列,排名为i的后缀记为SA[i] 额外地,我们考虑排名为i的后缀与排名为 i-1的后缀,把二者的最长公共前缀的长度记为hgt[i]使用快排......
  • error: rpmdb: BDB0113 Thread/process 14536/140712790841152 failed: BDB1507 Threa
    yumremovedockererror:rpmdb:BDB0113Thread/process14536/140712790841152failed:BDB1507ThreaddiedinBerkeleyDBlibraryerror:db5error(-30973)fromdb......
  • 2022-12-01 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • 一本通1456(哈希表板子
     用map<int,bool> #include"bits/stdc++.h"usingnamespacestd;constintN=1e4+5;#defineintunsignedlonglongconstintmod=212370440130137957ll;cha......
  • acwing131. 直方图中最大的矩形
     #include"bits/stdc++.h"usingnamespacestd;constintN=1e5+3;#defineintlonglongintn,a[N];inthh,stk[N],w[N];voidsov(){hh=0;m......
  • 代码随想录算法训练营Day14|144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉
    代码随想录算法训练营Day14|144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历144.二叉树的前序遍历144.二叉树的前序遍历递归遍历/***Defini......
  • POJ - 1456 Suprtmarket
    POJ-1456Suprtmarket题目大意:传送门有\(n\)个物品,第\(i\)个物品必须要在\(d_i\)天内买完,且卖出该物品可以获得\(p_i\)的利润。一天只能卖一个物品,求最多可以获得多少......
  • acw 120. 防线
    给一些区间【l,r】,区间i内间隔d[i]有一个点(可能会重复),保证最后只有一个位置的点数为奇数,其他位置的点数为偶数找出这个点 二分查找二分点的位置,注意题目中唯......
  • 【UVA 1451】Average
    题意:给出一个长度为n的01序列,要你求出一段至少长度为L的连续子序列,该子序列的数字的平均值最大,多解尽量保证长度小,在保证起点编号尽量小,求出起点和终点编号。......