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. }

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Sinh Test trong Python va code AC

P1: #file = "C:/New folder/aka/1.inp" #with open(file) as f: # a,b=[int(x) for x in next(f).split()] #print(a) #print(b) def gg(id): file= "C:/New folder/aka/" +id+ ".inp" with open (file) as f: a,b=[ int (x) for x in next (f).split()] products = set () for pair in [(x,y) for x in range ( 2 ,a+ 1 ) for y in range ( 2 ,b+ 1 )]: products.add(pair[ 0 ]**pair[ 1 ]) return len (products) x= range ( 1 , 101 ) for i in x: id= str (i) file1 = "C:/New folder/aka/" +id+ ".out" f= open (file1, "w" ) f.write( str (gg(id))) f.close() P2: a,b=[ int (x) for x in input ().split()] product = set () for pair in [(x,y) for x in range ( 2 ,a+ 1 ) for y in range ( 2 ,b+ 1 )]: product.add(pair[ 0 ]**pair[ 1 ]) print ( len (product))
Đọc thêm

Cách tính a*b mod m , a^b mod m , a^(-1) mod m với m không phải là số nguyên tố (inversion có nghĩa khi (a,m)=1)

#include <bits/stdc++.h> using namespace std ; #define ll long long #define MOD (ll)(1000000000000000009) ll inv ( ll a , ll mod ){ ll r = mod ; ll nr = a ; ll t = 0 ; ll nt = 1 ; ll tmp ; while ( nr != 0 ){ ll q = r / nr ; tmp = nt ; nt = t - q * nt ; t = tmp ; tmp = nr ; nr = r - q * nr ; r = tmp ; } if ( r > 1 ) return - 1 ; // no inverse if ( t < 0 ) t += mod ; return t ; } ll f ( ll a , ll n , ll mod ){ ll res = a , ans = 0 ; while ( n ){ if ( n % 2 ) ans = ( ans + res ) % mod ; res = ( res + res ) % mod ; n /= 2 ; } return ans ; } ll po ( ll a , ll n , ll mod ){ ll res = a , ans = 1 ; while ( n ){ if ( n % 2 ) ans = f ( ans , res , mod ); res = f ( res , res , mod ); n /= 2 ; } return ans ; } int main (){ ll x , y , z , m , dem = 0 , res1 , res2 , res , tmp
Đọc thêm

Python - Liệt kê tất các các chu trình trong đồ thị

graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]] cycles = [] def main(): global graph global cycles for edge in graph: for node in edge: findNewCycles([node]) for cy in cycles: path = [str(node) for node in cy] s = ",".join(path) print(s) def findNewCycles(path): start_node = path[0] next_node= None sub = [] #visit each edge and each node of each edge for edge in graph: node1, node2 = edge if start_node in edge: if node1 == start_node: next_node = node2 else: next_node = node1 if not visited(next_node, path): # neighbor node not on path yet sub = [next_node] sub.extend(path) # explore extended path findNewCycles(sub); e
Đọc thêm