Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- struct cap{
- ll a,b;
- };
- bool cmp(cap x, cap y){
- if(x.b==y.b) return x.a>y.a;
- return x.b>y.b;
- }
- int main(){
- ll n;
- cin>>n;
- cap oke[n];
- ll i;
- for(i=0;i<n;i++){
- cin>>oke[i].a>>oke[i].b;
- }
- sort(oke,oke+n,cmp);
- ll res=0;
- for(i=0;i<n;i++){
- res=res+oke[i].b;
- }
- res=min(n,res+1);
- ll ans=0;
- for(i=0;i<res;i++){
- ans=ans+oke[i].a;
- }
- cout<<ans;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét