一流的微商城网站建设wordpress 文章 分类 页面

一流的微商城网站建设,wordpress 文章 分类 页面,企业网站建设周期,自己搭建云手机服务器【题目描述】小明在一次聚会中#xff0c;不慎遗失了自己的钱包#xff0c;在接下来的日子#xff0c;面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下#xff0c;老板最终同意延缓账单的支付时间。可老板又提出#xff0c;必须从目前还没有支付的所有账…【题目描述】小明在一次聚会中不慎遗失了自己的钱包在接下来的日子面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下老板最终同意延缓账单的支付时间。可老板又提出必须从目前还没有支付的所有账单中选出面额最大和最小的两张并把他们付清。还没有支付的账单会被保留到下一天。 请你帮他计算出支付的顺序。【输入】第1行一个正整数N(N≤15,000)表示小明补办银联卡总共的天数。第2行到第N1 行每一行描述一天中收到的帐单。先是一个非负整数M≤100表示当天收到的账单数后跟M个正整数都小于1,000,000,000表示每张帐单的面额。输入数据保证每天都可以支付两张帐单。【输出】输出共N 行每行两个用空格分隔的整数分别表示当天支付的面额最小和最大的支票的面额。【输入样例】4 3 3 6 5 2 8 2 3 7 1 7 0【输出样例】3 6 2 8 1 7 5 7这是一个非常经典的“动态维护极值”问题。既然题目不难我们直接切入重点对比两种解法的优劣和核心技巧。1. 题目本质我们需要维护一个账单池支持以下三种操作且每天都要执行Insert插入若干个新数值。Pop Max查询并删除最大值。Pop Min查询并删除最小值。2. 解法一STL Multiset最简捷利用 Cmultiset底层红黑树自动排序的特性它是解决此类问题的“万能钥匙”。思路所有数据丢进去它自动排好序。最小值*st.begin()最大值*st.rbegin()代码优势极短逻辑极其简单不易出错。关键避坑删除时必须用迭代器st.erase(it)绝不能用st.erase(val)。后者会把所有同金额的账单一次性删光导致 BUG。删除最大值推荐用st.erase(prev(st.end()))。3. 解法二双堆 懒惰删除最高效利用两个优先队列分别维护最大值和最小值。这是解决“堆不支持随机删除”的标准范式。思路双倍存储每个账单同时进入maxq和minq并绑定唯一id。懒惰删除 (Lazy Deletion)当我们在 maxq 删除了一个元素无法直接去 minq 里删它太慢。于是我们在 deleted 数组里标记该 id 为“已删除”。等到 minq 的堆顶恰好浮现出这个“已删除”的元素时再把它弹出丢掉。工程细节while循环清理“死元素”时最好加上!q.empty()防止越界虽然本题数据保证不空但这是好习惯。4. 总结与对比维度Multiset 解法双堆 懒惰删除 解法代码量极少中等思维难度无脑需理解延迟删除运行效率较慢 (红黑树常数大)极快(堆操作常数小)适用场景比赛省时间、数据量中等卡常数、追求极致性能完整代码/* //直接用multiset 可以直接得到最大值和最小值 #include iostream #include set//必须包含这个头文件 #include algorithm using namespace std; //使用multiset,因为它会自动排序,且允许有重复的账单金额 multisetintst; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cinn; for(int i1;in;i){ int cnt;cincnt; //1.把今天的账单全部扔进set for(int j1;jcnt;j){ int tmp; cintmp; st.insert(tmp);//O(log N)自动排序 } //2.取出并删除最小值 //st.begin()就是最小值的迭代器 int mi*st.begin(); st.erase(st.begin());//注意:要用迭代器删除,否则会删除所有等于mi的元素 //3.取出并删除最大值 //st.rbegin()是反向迭代器的开始,指向最大值 //或者用prev(st.end())也可以找到最大值 int ma*st.rbegin(); //删除最大值(需要将反向迭代器转为正向迭代器,或者直接删除尾部前一个) //最简单的写法是删除迭代器:prev(st.end())指向最后一个元素 st.erase(prev(st.end())); //输出 coutmi ma\n; } return 0; } */ //用优先队列 #include iostream #include queue using namespace std; int deleted[1500001]; priority_queuepairint,int maxq;//默认最大堆 priority_queuepairint,int,vectorpairint,int,greaterpairint,int minq;//最小堆 int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cinn; int id0; for(int i1;in;i){//总共有n天 int cnt;//每天有cnt张账单 cincnt; for(int j1;jcnt;j){ int val; cinval; id; maxq.push({val,id}); minq.push({val,id}); } while(!maxq.empty() deleted[maxq.top().second]1){//如果最大堆堆顶的数的id已经被标记为在最小堆里删除了就直接弹出 maxq.pop();//如果最大堆堆顶的数的id已经被标记为在最小堆里删除了就直接弹出 } int mamaxq.top().first;//最大堆的最大值 deleted[maxq.top().second]1;//标记这个最大值的id为1已被删除后面不能被最小堆拿来用了 maxq.pop();//把最大堆的最大值弹出 while(!minq.empty() deleted[minq.top().second]1){//如果最小堆堆顶的数的id已经被标记为在最大堆里删除了就直接弹出 minq.pop();//如果最小堆堆顶的数的id已经被标记为在最大堆里删除了就直接弹出 } int miminq.top().first;//最小堆的最小值 deleted[minq.top().second]1;//标记这个最小值的id为1已被删除后面不能被最大堆拿来用了 minq.pop(); coutmi ma \n; } return 0; }在比赛中如果时间允许N10^5优先用 Multiset 如果数据量极大或时限很紧必须掌握双堆懒惰删除。