洛谷P3545 题解
洛谷P3545（原题指路）很典的一道带反悔贪心
题意简述
一共\(n\) 天。
第 \(i\) 天上午进货 \(ai\) 件商品，中午有一个顾客需要 \(bi\) 件商品，可以满足他或无视他。
要满足顾客则必须要有足够的库存。问最多能满足多少位顾客，以及能满足的是哪些顾客。
解题思路
（带反悔贪心）
开一个堆存储顾客信息，其中购货量多的顾客在上。
开一个数组记录顾客是否被满足。
用ans记录满足了的顾客的数量。
遍历 \(1-n\) 的每一天。
接下来分两种情况：
[*]如果当天进货后库存足够，则直接满足顾客的需求，记录满足了该顾客，并且把他的信息存入堆中
[*]如果当天进货后库存不足，则弹出堆顶元素 \(lins\) ，并且比较当前顾客与 \(lins\) 顾客的信息
[*]如果lins的购货量多于当前顾客，则同样是多满足了一个顾客，满足当前顾客时剩余的存货量要多于满足lins顾客时剩余的存货量。则此时满足当前顾客比满足 \(lins\) 顾客更优。因此反悔满足 \(lins\) 顾客的决定——将 \(lins\) 顾客的信息从堆中删除（删除堆顶元素），并且将 \(lins\) 顾客标记为没有满足；将当前顾客标记为满足，并将他的信息存入堆中。
[*]反之，如果 \(lins\) 的购货量少于当前顾客，那么维持原状比反悔并满足当前顾客更优，则直接无视当前顾客即可
最后输出ans；并且遍历标记数组，若顾客被满足则输出其编号。
代码展示
#include#define int long longusing namespace std;int n,hw,ans;bool vis;struct node{ int a,b,bh;}mm;struct cmp{ bool operator() (node x,node y){ return x.b 这个有用。 不错，里面软件多更新就更好了 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了 热心回复！ 这个好，看起来很实用 yyds。多谢分享 不错，里面软件多更新就更好了 不错，里面软件多更新就更好了 过来提前占个楼 这个有用。 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 感谢发布原创作品，程序园因你更精彩 这个有用。 鼓励转贴优秀软件安全工具和文档！ 鼓励转贴优秀软件安全工具和文档！ 热心回复！ 很好很强大我过来先占个楼 待编辑
页:
[1]
2