Thứ Tư, 2 tháng 12, 2020

Cho n thẻ bài có dạng (a_i,b_i). Ban đầu ta bốc một thẻ bất kì, khi đó số điểm sẽ được cộng thêm a_i và ta sẽ có quyền bốc thêm b_i cái thẻ nữa. Tìm số điểm tối đa mà ta có thể thu được

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

 Tóm tắt:Cho n thẻ bài có dạng (a_i,b_i). Ban đầu ta bốc một thẻ bất kì, khi đó số điểm sẽ được cộng thêm a_i và ta sẽ có quyền bốc thêm b_i cái thẻ nữa. Tìm số điểm tối đa mà ta có thể thu được

Lời giải: Bài này ta chỉ việc sắp xếp lại và sau đó cộng tổng là xong

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. struct cap{
  5. ll a,b;
  6. };
  7. bool cmp(cap x, cap y){
  8. if(x.b==y.b) return x.a>y.a;
  9. return x.b>y.b;
  10. }
  11. int main(){
  12. ll n;
  13. cin>>n;
  14. cap oke[n];
  15. ll i;
  16. for(i=0;i<n;i++){
  17. cin>>oke[i].a>>oke[i].b;
  18. }
  19. sort(oke,oke+n,cmp);
  20. ll res=0;
  21. for(i=0;i<n;i++){
  22. res=res+oke[i].b;
  23. }
  24. res=min(n,res+1);
  25. ll ans=0;
  26. for(i=0;i<res;i++){
  27. ans=ans+oke[i].a;
  28. }
  29. cout<<ans;
  30. return 0;
  31. }

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