Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- vector<pair<ll,ll> > v1,v2;
- int main(){
- ll n;
- cin>>n;
- ll i;
- for(i=0;i<n;i++){
- ll u,v;
- cin>>u>>v;
- if(u<0) v1.push_back({u,v});
- else v2.push_back({u,v});
- }
- sort(v1.rbegin(),v1.rend());
- sort(v2.begin(),v2.end());
- ll res=0;
- if(v1.size()==v2.size()){
- for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
- cout<<res;
- return 0;
- }
- if(v1.size()>v2.size()){
- for(i=0;i<v2.size();i++) res=res+v1[i].second+v2[i].second;
- res=res+v1[v2.size()].second;
- cout<<res;
- return 0;
- }
- if(v1.size()<v2.size()){
- for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
- res=res+v2[v1.size()].second;
- cout<<res;
- return 0;
- }
- }
Không có nhận xét nào:
Đăng nhận xét