Thứ Hai, 30 tháng 11, 2020

Bạn đang ở vị trí 0, và có các cây táo ở vị trí trên trên tọa độ. Ban đầu bạn có thể chọn qua trái hoặc phải tùy ý. Sau đó đi, gặp cây nào hái hết táo cây đó và đi ngược lại. Hỏi số táo tối đa tìm được là bao nhiêu ?

Đề bài: $\href{https://codeforces.com/problemset/problem/558/A}{Đây}$

 Tóm tắt: Bạn đang ở vị trí 0, và có các cây táo ở vị trí trên trên tọa độ. Ban đầu bạn có thể chọn qua trái hoặc phải tùy ý. Sau đó đi, gặp cây nào hái hết táo cây đó và đi ngược lại. Hỏi số táo tối đa tìm được là bao nhiêu ?

Lời giải: Bài này ta sử dụng sắp xếp và một chút suy luận để xác định sang trái hay sang phải cho phù hợp là xong

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. vector<pair<ll,ll> > v1,v2;
  5. int main(){
  6. ll n;
  7. cin>>n;
  8. ll i;
  9. for(i=0;i<n;i++){
  10. ll u,v;
  11. cin>>u>>v;
  12. if(u<0) v1.push_back({u,v});
  13. else v2.push_back({u,v});
  14. }
  15. sort(v1.rbegin(),v1.rend());
  16. sort(v2.begin(),v2.end());
  17. ll res=0;
  18. if(v1.size()==v2.size()){
  19. for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
  20. cout<<res;
  21. return 0;
  22. }
  23. if(v1.size()>v2.size()){
  24. for(i=0;i<v2.size();i++) res=res+v1[i].second+v2[i].second;
  25. res=res+v1[v2.size()].second;
  26. cout<<res;
  27. return 0;
  28. }
  29. if(v1.size()<v2.size()){
  30. for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
  31. res=res+v2[v1.size()].second;
  32. cout<<res;
  33. return 0;
  34. }
  35. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...