题解 UVA1316 【Supermarket】
2024-09-03 22:43:56
题目链接：
思路：
根据题目意思，我们需要用到贪心的思想，越晚过期的商品当然是越晚卖好。同时你假如有多个商品必须在同一天卖出，当然是卖收益多的好。
于是我们就有以下方法：首先将每个商品的过期时间按从小到大排序，同时建立一个小根堆，然后遍历这些商品。
如果商品过期时间大于堆中商品个数，说明前面还有些天是没有卖东西的，当然可以把这个商品插入堆中。
类似的，如果商品过期时间等于堆中商品个数，就比较此商品的收益和堆顶的收益哪个大。如果堆顶的收益小，就把他POP出堆顶，然后将此商品插入到堆中；相反，如果堆顶的收益大，那就不进行操作。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn=10008;
struct Goods{
int p,d;
}s[maxn];
struct Small_Heap{
int n,heap[maxn];
inline void up(int fa){
while(fa>1){
if(heap[fa]<heap[fa>>1]){
swap(heap[fa],heap[fa>>1]);
fa=fa>>1;
}
else break;
}return ;
}
inline void insert(int v){
heap[++n]=v;
up(n);
return ;
}
inline void down(int fa){
int s=fa<<1;
while(s<=n){
if(s<n && heap[s]>heap[s+1])s++;
if(heap[s]<heap[fa]){
swap(heap[s],heap[fa]);
fa=s,s=fa<<1;
}
else break;
}return ;
}
inline void extract(){
heap[1]=heap[n--];
down(1);
}
inline int GetTop(){
return heap[1];
}
}a;
inline bool cmp(const Goods &a,const Goods &b){
return a.d<b.d;
}
template<class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int main()
{
int n,x;
while(cin>>n){
int ans=0; //堆中商品个数
for(register int i=1;i<=n;i++){
read(s[i].p),read(s[i].d);
}
sort(s+1,s+1+n,cmp);
// for(register int i=1;i<=n;i++)cout<<s[i].p<<' '<<s[i].d<<endl;
for(register int i=1;i<=n;i++){
if(s[i].d==a.n){
if(s[i].p>a.GetTop()){
a.extract();
a.insert(s[i].p);
}
}
else if(s[i].d>a.n){
a.insert(s[i].p);
}
}
for(register int i=1;i<=a.n;i++){
// cout<<a.heap[i]<<endl;
ans+=a.heap[i];
a.heap[i]=0;
}a.n=0;
printf("%d\n",ans);
}
return 0;
}
最新文章
- 【NLP】Python NLTK 走进大秦帝国
- PHP计算一年有多少周，每周开始日期和结束日期
- ZOJ3772 - Calculate the Function(线段树+矩阵)
- Asm Shader Reference --- Shader Model 2.x part
- virtualenv创建虚拟环境
- 04737_C++程序设计_第3章_函数和函数模板
- python 时间处理
- git 生成公钥、私钥方法与clone使用方法
- 服务器cpu100%问题分析
- iptables 学习
- is,as,类库
- iOS之Safari调试webView/H5页面
- SpringMVC.入门篇.一.HelloWorld
- 通过nginx + lua来统计nginx上的监控网络请求和性能
- Canvas中的剪切clip()方法
- JAVAEE学习——hibernate01：简介、搭建、配置文件详解、API详解和CRM练习:保存客户
- JAVA多线程------用1
- Navicat for MySQL导入文件
- MySQL 实现字符串换行
- CF1060D Social Circles