# February 13, 2020 winter holiday training eight (priority queue)

## Problem A: NEFU1537 buy Rice

```#include<bits/stdc++.h>
using namespace std;
struct node{
int t, No;
};
priority_queue<node, vector<node> > q;
bool operator < (const node &s1, const node &s2)
{
if(s1.t != s2.t) return s1.t > s2.t;
else return s1.No > s2.No;
}
int n, every_time;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>every_time;
q.push({every_time, i});
}
int ans=0, tmp=n;
while(!q.empty())
{
n--;
if(q.size() > 1)
cout<<q.top().No<<" ";
else cout<<q.top().No<<endl;
ans += (q.top().t)*n;
q.pop();
}
printf("%.2lf", ans*1.0/tmp);
return 0;
}
```

## Problem B: NEFU1688 merge fruit

You can use a pile or you can be greedy
(the essence of priority queue stl is heap)

```#include<bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
int main()
{
ios::sync_with_stdio(false);
int n, i, ans=0;
cin>>n;
while(n--)
{
cin>>i;
q.push(i);
}
while(q.size() > 1)
{
int t1=q.top();
q.pop();
int t2=q.top();
q.pop();
ans += t1+t2;
q.push(t1+t2);
}
cout<<ans<<endl;
return 0;
}
```

## Problem C: NEFU1689 sequence merging

Since the given data guarantees the order of a and B, a[1]+b[1] must be the smallest.
The size of a[i]+b[1], a[1]+b[i] is increasing

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll No, sum;
};
priority_queue<node, vector<node> > q;
bool operator < (const node &nod1, const node &nod2)
{
return nod1.sum > nod2.sum;
}
ll a[400005], b[400005];
int c[400005]; // Used for summation
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
scanf("%lld", &a[i]);
c[i] = 1; // Set the subscript to 1 first
}
for(int i=1; i<=n; i++)
scanf("%lld", &b[i]);
for(int i=1; i<=n; i++)
q.push({i, a[i]+b[1]}); // First a[i]+b[1]
for(int i=1; i<=n; i++)
{
node tmp = q.top();
printf("%lld\n", tmp.sum); // a[1]+b[1] must be minimum
c[tmp.No]++; // Subscript accumulation
q.pop();
tmp.sum = a[tmp.No]+b[c[tmp.No]]; // To update
q.push(tmp);
}
return 0;
}
```

## Problem D: NEFU355 synthetic meteorite

This topic is for many groups of input, so we should pay attention to the clearing every time.
You can apply for the queue in the while loop, or empty the queue after each operation (since there is only one element left after the queue operation, you can pop it directly).

```#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n, i, ans=0;
while(cin>>n)
{
priority_queue<int, vector<int>, greater<int> > q;
ans = 0; // Zero clearing
while(n--)
{
cin>>i;
q.push(i);
}
while(q.size() > 1)
{
int t1=q.top();
q.pop();
int t2=q.top();
q.pop();
ans += t1+t2;
q.push(t1+t2);
}
//q.pop() / / clear the queue
cout<<ans<<endl;
}
return 0;
}
```

## Problem E: NEFU1692 reactor

Template problem.

```#include<bits/stdc++.h>
using namespace std;
int n, m, num;
priority_queue<int, vector<int>, greater<int> > q;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
while(n--)
{
cin>>m;
switch(m)
{
case 1:
cin>>num;
q.push(num);
break;
case 2:
cout<<q.top()<<endl;
break;
default:
q.pop();
break;
}
}
return 0;
}
```

## Problem F: NEFU1691 wood board of Ruirui

Same as B. Pay attention to the data range.

```#include<bits/stdc++.h>
using namespace std;
priority_queue<long long, vector<long long>, greater<long long> > q;
int main()
{
ios::sync_with_stdio(false);
long long n, i, ans=0;
cin>>n;
while(n--)
{
cin>>i;
q.push(i);
}
while(q.size() > 1)
{
long long t1=q.top();
q.pop();
long long t2=q.top();
q.pop();
ans += t1+t2;
q.push(t1+t2);
}
cout<<ans<<endl;
return 0;
}
```

## Problem G: News system of NEFU1690 Tongtong

Yes dalao Say it's done with map, I won't, define more than one value for maintenance..

```#include<bits/stdc++.h>
using namespace std;
struct node{
int Q_num, period, st; // st is used to maintain the value of period
};
priority_queue<node, vector<node> > q;
bool operator<(const node &nod1, const node &nod2)
{
if(nod1.period != nod2.period) return nod1.period > nod2.period;
else return nod1.Q_num > nod2.Q_num;
}
int main()
{
ios::sync_with_stdio(false);
int k, num, per;
string str;
while(cin>>str)
{
if(str[0] == 'R')
{
cin>>num>>per;
q.push({num, per, per});
}
if(str[0] == '#') break;
}
cin>>k;
while(k--)
{
node tmp = q.top();
q.pop();
cout<<tmp.Q_num<<endl;
tmp.period += tmp.st;
q.push(tmp);
}
return 0;
}
```
53 original articles published, 36 praised, 10000 visitors+

Tags: iOS

Posted on Thu, 13 Feb 2020 09:47:54 -0800 by filn