当前位置：首页 > news >正文

题解：学而思编程动态绝对值最小

news 2026/6/11 19:06:12

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：动态绝对值最小

【题目描述】

有一个函数f ( x ) f(x)f(x)，初始是一个常数函数f ( x ) = 0 f(x)=0f(x)=0。你要处理Q QQ个任务，每个任务都是以下两种中的一种：

（1）更新1 a b：给你两个整数a , b a,ba,b，定义g ( x ) = f ( x ) + ∣ x − a ∣ + b g(x)=f(x)+∣x−a∣+bg(x)=f(x)+∣x−a∣+b。然后用g ( x ) g(x)g(x)替换f ( x ) f(x)f(x)（即令f ( x ) = g ( x ) f(x)=g(x)f(x)=g(x)）。

（2）求值2：输出使得f ( x ) f(x)f(x)取最小值的x xx，和f ( x ) f(x)f(x)的最小值。如果有多个x xx可以使f ( x ) f(x)f(x)取到最小，取其中最小的x xx。

可以证明，求值时的输出一定是整数。

【输入】

第1 11行，1 11个正整数Q QQ。

接下来Q QQ行，每行一个任务。第1 11个数表示任务种类，1 11表示更新，2 22表示求值。对于更新操作，后面还会有两个整数a , b a,ba,b。

【输出】

对每个求值操作，用一行输出两个整数，用空格隔开。分别表示使得f ( x ) f(x)f(x)取最小值的x xx，和f ( x ) f(x)f(x)的最小值。如果有多个x xx可以使f ( x ) f(x)f(x)取到最小，取其中最小的x xx。

【输入样例】

4 1 4 2 2 1 1 -8 2

【输出样例】

4 2 1 -3

【算法标签】

#堆排序

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongpriority_queue<int>small;// 大根堆，存储较小的一半priority_queue<int,vector<int>,greater<int>>big;// 小根堆，存储较大的一半intQ,zl,a[200005],b,cur,ans,sumb,sums;// Q: 查询次数，zl: 操作类型，a: 存储插入的数，b: 代价// cur: 当前插入的数量，ans: 所有b的和，sumb: big堆中元素和，sums: small堆中元素和signedmain(){cin>>Q;// 输入查询次数while(Q--){cin>>zl;// 输入操作类型if(zl==1)// 操作1：插入{cin>>a[++cur]>>b;// 输入插入的数x和代价bans+=b;// 累加所有b// 将x插入到合适的堆中if(!small.empty()&&a[cur]>small.top())// 如果x大于small堆的最大值{big.push(a[cur]);// 插入到big堆sumb+=a[cur];// 更新big堆元素和}else{small.push(a[cur]);// 否则插入到small堆sums+=a[cur];// 更新small堆元素和}// 平衡两个堆，保持small堆比big堆最多多1个元素if(small.size()>big.size()+1)// 如果small堆太大{big.push(small.top());// 将small堆的最大值移到big堆sums-=small.top();// 更新sumssumb+=small.top();// 更新sumbsmall.pop();// 从small堆移除}elseif(small.size()<big.size())// 如果big堆更大{small.push(big.top());// 将big堆的最小值移到small堆sums+=big.top();// 更新sumssumb-=big.top();// 更新sumbbig.pop();// 从big堆移除}}else// 操作2：查询{intx=small.top();// 中位数（或第k小的数）cout<<x<<' ';// 输出中位数// 计算总代价：ans + Σ|x - a[i]|intlsum=x*small.size()-sums;// small堆中所有数与x的差值和intrsum=sumb-x*big.size();// big堆中所有数与x的差值和intres=ans+lsum+rsum;// 总代价cout<<res<<endl;}}}