Priority Queue - Xuoi - Nguoc

 Nguồn: https://codeforces.com/problemset/problem/218/B

Solve:

1. //priority_queue <int> ; less
2. //priority_queue <int,vector<int>,greater<int> > ; greater
3. #include<bits/stdc++.h>
4. using namespace std;
5. #define ll long long
6. priority_queue <ll> q_max;
7. priority_queue<ll,vector<ll>,greater<ll>> q_min;
8. int main(){
9. ll n,m;
10. cin>>n>>m;
11. ll i;
12. ll a[m];
13. for(i=0;i<m;i++){
14. cin>>a[i];
15. q_max.push(a[i]);
16. q_min.push(a[i]);
17. }
18. ll res_max=0, res_min=0;
19. for(i=0;i<n;i++){
20. ll q;
21. ll p;
22. q = q_max.top();
23. p = q_min.top();
24. q_max.pop();
25. q_min.pop();
26. if(q>0&&p>0){
27. res_max=res_max+q;
28. res_min=res_min+p;
29. q--;p--;
30. if(q>0) q_max.push(q);
31. if(p>0) q_min.push(p);
32. }
33. }
34. cout<<res_max<<" "<<res_min<<'\n';
35. return 0;
36. }