Đề bài: $\href{https://codeforces.com/problemset/problem/570/A}{Đây}$
Tóm tắt: Cho n ứng cử viên và m thành phố cùng với ma trận m*n với aij thể hiện số phiếu do thành phố thứ i bầu cho ứng cử viên thứ j. Tìm ứng cử viên xuất sắc nhất thỏa mãn điều kiện sau: Xét trong cùng một thành phố, ứng cử viên nào có số phiếu cao nhất thì sẽ được chọn (nếu có nhiều người cùng số phiếu, thì chọn người có chỉ số thấp nhất). Sau khi chọn người giỏi nhất từng thành phố, tiếp tục ta xét, người nào có số thành phố chọn mình nhiều nhất thì sẽ được chọn (nếu nhiều người có cùng số thành phố, thì chọn người có chỉ số thấp nhất).
Lời giải: Đây là bài thuần sắp xếp, nhưng ở mức độ kĩ thuật, để hiểu rõ hơn các bạn có thể xem source:
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- vector<pair<ll,ll> > v,v1,v2;
- map<ll,ll> mt;
- bool cmp(pair<ll,ll> uu, pair<ll,ll> vv){
- if(uu.first==vv.first) return uu.second<vv.second;
- return uu.first>vv.first;
- }
- int main(){
- ll city, candidate;
- cin>>candidate>>city;
- ll a[city][candidate];
- ll i,j;
- for(i=0;i<city;i++)
- for(j=0;j<candidate;j++) cin>>a[i][j];
- for(i=0;i<city;i++){
- v.clear();
- for(j=0;j<candidate;j++) v.push_back({a[i][j],j});
- sort(v.begin(),v.end(),cmp);
- v1.push_back({i,v[0].second});
- }
- // sort(v1.begin(),v1.end(),cmp);
- // cout<<v1[0].second+1;
- for(auto p: v1){
- mt[p.second]++;
- }
- for(auto p: mt){
- v2.push_back({p.second,p.first});
- }
- sort(v2.begin(),v2.end(),cmp);
- cout<<v2[0].second+1;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét