Chủ Nhật, 22 tháng 11, 2020

Cho n cặp số lượng x,y ; số nguyên dương d và cặp số a,b. Hỏi có ta có thể thu được tối đa bao nhiêu cặp x,y sao cho tổng các x*a+y*b không quá d

 Đề bài: $\href{https://codeforces.com/contest/203/problem/C}{Đây}$

Tóm tắt: Cho n cặp số lượng x,y ; số nguyên dương d và cặp số a,b. Hỏi có ta có thể thu được tối đa bao nhiêu cặp x,y sao cho tổng các x*a+y*b không quá d

Lời giải: Ở đây ta dùng tham lam

Source: 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. vector<pair<ll,ll> > cc;
  5. vector<ll> res;
  6. int main(){
  7. ll n,d;
  8. cin>>n>>d;
  9. ll a,b;
  10. cin>>a>>b;
  11. for(ll i=0;i<n;i++){
  12. ll x,y;
  13. cin>>x>>y;
  14. ll tmp;
  15. tmp = a*x+b*y;
  16. cc.push_back({tmp,i});
  17. }
  18. sort(cc.begin(),cc.end());
  19. for(auto p: cc){
  20. if(d>=p.first){
  21. res.push_back(p.second+1);
  22. d-=p.first;
  23. }
  24. else break;
  25. }
  26. cout<<res.size()<<'\n';
  27. for(auto p: res) cout<<p<<" ";
  28. }

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