OJ exercise on February 13, 2020 [priority queue]

First, let's distinguish between priority queues and queues

Definition

: priority_queue<type,vector,less(greater) >q;

(note that the last two > should have spaces in between, otherwise the compiler might think it's a right shift.)
Among them, type can make int, long long, etc., but it is generally a custom structure, that is, priority queue is often associated with the structure;
It should be noted that the sorting here is the opposite of sort. Less is sorting from large to small, while greater is sorting from small to large. If the third variable is not written and there is no custom sorting, the default is less, that is, from large to small;

Custom sort writing

: struct pa

{

int t;

int id;

};

bool operator < (const pa &a,const pa &b)

This sentence is written in a fixed way. Just remember it. It's indispensable

{

if(a.t!=b.t) return a.t>b.t;

else return a.id>b.id;

}

At this time, the structure is generally used, but it should be remembered that the cmp sorting of sort is exactly the opposite;
Also, the first element of the priority queue is:

q.top();

Merge fruit - priority queue

Basic priority questions

Idea: first put the fruits in the priority queue sorted from small to large, then find them two by two, and then put the sum of the two into the queue until they are found.

#include <bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,greater<int> >x;
int n,a[10005],sum=0,s1,s2;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        x.push(a[i]);
    while(1)
    {
        s1=x.top();
        x.pop();
        s2=x.top();
        x.pop();
        sum+=(s1+s2);
        if(x.empty()) break;
        x.push(s1+s2);
    }
    cout<<sum<<endl;
    return 0;
}

Synthetic meteorite - priority formation

It has the same idea as the previous question, but it's just multiple sets of inputs

#include <bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,greater<int> >x;
int n,a[10005],sum=0,s1,s2;
int main()
{
    while(cin>>n)
    {
        sum=0;
         for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        x.push(a[i]);
    while(1)
    {
        s1=x.top();
        x.pop();
        s2=x.top();
        x.pop();
        sum+=(s1+s2);
        if(x.empty()) break;
        x.push(s1+s2);
    }
    cout<<sum<<endl;
    }
    return 0;
}

Buy Rice - priority queue

The idea is to arrange the time in ascending order. The shorter the time in front of you is, the shorter the waiting time will be. There is also the method to calculate the average waiting time of everyone
**Suppose there are n people, then the last one has to wait for the meal time of n-1 people, and so on. Finally, the first one has been waiting for n-1 times, the second one has been waiting for N-2 times...... The average waiting time is: (a[1]*N-1+a[2]*N-2 + +a[N-1]1+a[N]0)/N;

#include <bits/stdc++.h>
using namespace std;

struct pa
{
    int t;//time
    int id;//Number at the beginning
};
bool operator < (const pa &a,const pa &b)
{
    if(a.t!=b.t) return a.t>b.t;//Ascending order
    else return a.id>b.id;
}
priority_queue<pa,vector<pa> >x;
int n,a[1005];
int main()
{
    struct pa tmp;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        x.push({a[i],i});
    }
    int j=n-1;
    double sum=0;
    for(int i=1;i<n;i++)
    {
        tmp=x.top();
        x.pop();
        sum+=j*tmp.t;
        j--;
        cout<<tmp.id<<" ";
    }
    tmp=x.top();
    x.pop();
    cout<<tmp.id<<endl;
    printf("%.2lf\n",sum/n);
    return 0;
}

Heap priority queue

This is simple. It is to write out the first elements of the priority queue step by step

#include <bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,greater<int> >x;
long long n,q,m;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        if(m==1)
        {
            cin>>q;
            x.push(q);
        }
        if(m==2)
            cout<<x.top()<<endl;
        if(m==3)
            x.pop();
    }
    return 0;
}

Ruirui's board - priority queue

This question was wrong several times at the beginning, because it still didn't understand the meaning of the question, and only after glancing at the solution of jwGG's question, the meaning of the question is the reverse process of merging fruits, which is essentially the same;
I firmly believe that it is the most economical to cut the boards of the desired length one by one in descending order, but this is wrong, because in fact, in the process, you can cut a board into two boards of different lengths, and then cut the two boards separately, so sometimes it is the most economical, so the essence of this question is The fruits are the same

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<int,vector<int>,greater<int> >x;
int n,a[20005],s1,s2;
ll sum=0;//long long is required to fit
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        x.push(a[i]);
    }
    while(x.size()>1)
    {
        s1=x.top();
        x.pop();
        s2=x.top();
        x.pop();
        sum+=(s1+s2);
        x.push(s1+s2);
    }
    cout<<sum<<endl;
    return 0;
}

Next two questions are to see the solution to understand how to write

Sequence merge - priority queue

Here is the idea of jwGG:
First, sequence A and B from small to large, respectively, into two ordered queues. In this way, N2 sums can be obtained by adding any number in A and B. these sums can be regarded as forming n ordered tables / queues:
A[1]+B[1] <= A[1]+B[2] <= ... <= A[1]+B[N]
A[2]+B[1] <= A[2]+B[2] <= ... <= A[2]+B[N]
......
A[N]+B[1] <= A[N]+B[2] <= ... <= A[N]+B[N]
Next, it is equivalent to merging and sorting these N ordered queues:
First, put the first element of the N queues into a priority queue;
Then, the minimum value in the heap is taken out each time. If the minimum comes from queue k, the next element of queue k is put in the heap.
Time complexity: O(NlogN).
The key is how to write to achieve the above operations. This is my short board now
It can be defined as a structure. Two variables x and y are used to control which two numbers are multiplied

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ad
{
    int x,y;
    ll sum;
};
bool operator < (const ad &a,const ad &b)
{
    return a.sum>b.sum;
}
priority_queue<ad,vector<ad> >q;
const int N=4e5+10;
int n,a[N],b[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        q.push({i,1,a[i]+b[1]});//First, put the product of the number in a and the first number in b into the priority queue
    for(int i=1;i<=n;i++)
    {
        struct ad tmp=q.top();
        q.pop();
        printf("%d\n",tmp.sum);
        int x=tmp.x,y=tmp.y;
        q.push({x,y+1,a[x]+b[y+1]});//The number out of the queue is the one in a. put the product of this number and the corresponding next number in b into the priority queue
    }
    return 0;
}

Tongtong's news system priority queue

This question is similar to the previous one

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ad
{
    int id,t,sum;//t is the original interval time; sum is the cumulative time, and the sorting is based on this
};
bool operator < (const ad &a,const ad &b)
{
    if(a.sum!=b.sum) return a.sum>b.sum;
    else return a.id>b.id;
}
priority_queue<ad,vector<ad> >q;
char str[10];
int k,id,t;

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>str&&str[0]!='#')
    {
        cin>>id>>t;
        q.push({id,t,t});//At the beginning, sum was t
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        struct ad tmp=q.top();
        q.pop();
        printf("%d\n",tmp.id);
        id=tmp.id;
        t=tmp.t;
        q.push({id,t,(t+tmp.sum)});//For those who are out of the team, a corresponding original interval should be added when they enter the team again
    }
    return 0;
}

Thank you jwGG!!!!!! Sure enough, I'm still too rubbish. I'd better stop following the white whoring course. It's too difficult to enter the laboratory hhh

Published 16 original articles, won praise 1, visited 302
Private letter follow

Tags: less iOS

Posted on Wed, 12 Feb 2020 23:19:01 -0800 by Reformed