1102: 序列合并
1、本质还是双层循环,但是b数组的下标巧妙地递增(b的下标存在结构体中,只有当找到一个最小节点时才往后增一次,这样一来就可以保证 { b【0】与a数组中所有的加数得到的和}、{b【1】与a数组中当前最小的数相加的和} 一起在优先队列中比较(自动排序)避免了超时
由于最小的数可以确定,要找到下一个最小的数,把两个加数都增加
显然不对,而应该保持一个加数不变,另一个加数递增一次
由于a数组中所有的数都和bmin组成了和,a所有数都可以进行比较
于是只要将b数组提供的这个加数往后递增,在当前找到的最小数的基础上
2、
在结构体里定义比较规则重载<时卡了一下
照常把return this->sum
要么改变小于号比较规则,反过来,
要么priority_queue(node,vector,greater >
我比你大,我把你推上去,让你先出队
sort 默认会根据小于号将元素从小到大排序;
priority_queue 中的元素默认是根据小于号的比较规则将最大的作为其堆顶元素。这个跟 sort 的思路有点不一样,
priority_queue 是 “我比你小,则我把你推到顶上去” 的意思。就是说,默认情况下,priority_queue 中的元素总是最大的那个作为堆顶元素。
所以默认的 priority_queue 是一个大顶堆。
#include#include #include using namespace std; const int MAX=100005; typedef long long int ll; ll a[MAX]; ll b[MAX]; struct node{ int index; ll sum; node(int i,ll s):index(i),sum(s){}; bool operator <(const node& n)const{ return sum>n.sum; } }; priority_queue >Q; int main(){ int n; cin>>n; for(int i=0;i >a[i]; } for(int i=0;i >b[i]; } sort(a,a+n); sort(b,b+n); for(int i=0;i



