Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- vector<pair<ll,ll> > cc;
- vector<ll> res;
- int main(){
- ll n,d;
- cin>>n>>d;
- ll a,b;
- cin>>a>>b;
- for(ll i=0;i<n;i++){
- ll x,y;
- cin>>x>>y;
- ll tmp;
- tmp = a*x+b*y;
- cc.push_back({tmp,i});
- }
- sort(cc.begin(),cc.end());
- for(auto p: cc){
- if(d>=p.first){
- res.push_back(p.second+1);
- d-=p.first;
- }
- else break;
- }
- cout<<res.size()<<'\n';
- for(auto p: res) cout<<p<<" ";
- }
Không có nhận xét nào:
Đăng nhận xét