洛谷P3545 题解

洛谷P3545（原题指路）

很典的一道带反悔贪心

题意简述

一共  \(n\) 天。
第 \(i\) 天上午进货 \(ai\) 件商品，中午有一个顾客需要 \(bi\) 件商品，可以满足他或无视他。
要满足顾客则必须要有足够的库存。问最多能满足多少位顾客，以及能满足的是哪些顾客。
解题思路

（带反悔贪心）

开一个堆存储顾客信息，其中购货量多的顾客在上。
开一个数组记录顾客是否被满足。
用ans记录满足了的顾客的数量。
遍历 \(1-n\) 的每一天。
接下来分两种情况：

• 如果当天进货后库存足够，则直接满足顾客的需求，记录满足了该顾客，并且把他的信息存入堆中
  
• 如果当天进货后库存不足，则弹出堆顶元素 \(lins\) ，并且比较当前顾客与 \(lins\) 顾客的信息
  
  
  
  • 如果lins的购货量多于当前顾客，则同样是多满足了一个顾客，满足当前顾客时剩余的存货量要多于满足lins顾客时剩余的存货量。则此时满足当前顾客比满足 \(lins\)　顾客更优。因此反悔满足 \(lins\) 顾客的决定——将 \(lins\) 顾客的信息从堆中删除（删除堆顶元素），并且将 \(lins\) 顾客标记为没有满足；将当前顾客标记为满足，并将他的信息存入堆中。
    
  • 反之，如果 \(lins\) 的购货量少于当前顾客，那么维持原状比反悔并满足当前顾客更优，则直接无视当前顾客即可
    
  
  

最后输出ans；并且遍历标记数组，若顾客被满足则输出其编号。
代码展示

[code]#include#define int long longusing namespace std;int n,hw,ans;bool vis[250010];struct node{        int a,b,bh;}mm[250010];struct cmp{        bool operator() (node x,node y){                return x.b