Đề bài: $\href{https://codeforces.com/problemset/problem/471/B}{Đây}$
Tóm tắt: Cho một mảng A gồm n phần tử. Nhiệm vụ của ta là tìm ra ba dãy chỉ số khác nhau thỏa mãn dãy đó không giảm.
Lời giải: Ý tưởng bài này chúng ta sẽ sử dụng map để giải quyết !
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- map<ll,vector<ll> > mt;
- vector<ll> res1,res2,res3;
- int main(){
- ll n;
- cin>>n;
- ll a[n];
- ll i;
- for(i=0;i<n;i++) {
- cin>>a[i];
- mt[a[i]].push_back(i);
- }
- ll dau=0,cnt=0;
- // for(auto p: mt){
- // cout<<p.first<<"---";
- // for(auto k: p.second) cout<<k<<" ";
- // cout<<'\n';
- // }
- for(auto p: mt){
- if(p.second.size()>=3) {dau=2;break;}
- else if(p.second.size()==2) cnt++;
- if(cnt==2) {dau=1;break;}
- }
- if(dau==0) {cout<<"NO"; return 0;}
- if(dau==2){
- for(auto p: mt){
- if(p.second.size()<=2)
- for(auto k: p.second) {
- res1.push_back(k);
- res2.push_back(k);
- res3.push_back(k);
- }
- if(p.second.size()>=3){
- sort(p.second.begin(),p.second.end());
- for(auto pp: p.second) res1.push_back(pp);
- next_permutation(p.second.begin(),p.second.end());
- for(auto pp: p.second) res2.push_back(pp);
- next_permutation(p.second.begin(),p.second.end());
- for(auto pp: p.second) res3.push_back(pp);
- }
- }
- }
- else if(dau==1){
- for(auto p: mt){
- if(p.second.size()<=1)
- for(auto k: p.second) {
- res1.push_back(k);
- res2.push_back(k);
- res3.push_back(k);
- }
- if(p.second.size()>=2&&cnt==2){
- sort(p.second.begin(),p.second.end());
- for(auto pp: p.second) res1.push_back(pp);
- for(auto pp: p.second) res2.push_back(pp);
- next_permutation(p.second.begin(),p.second.end());
- for(auto pp: p.second) res3.push_back(pp);
- cnt-=1;
- continue;
- }
- if(p.second.size()>=2&&cnt==1){
- sort(p.second.begin(),p.second.end());
- for(auto pp: p.second) res1.push_back(pp);
- next_permutation(p.second.begin(),p.second.end());
- for(auto pp: p.second) res2.push_back(pp);
- for(auto pp: p.second) res3.push_back(pp);
- cnt-=1;
- continue;
- }
- if(p.second.size()>=2&&cnt==0){
- for(auto pp: p.second) res1.push_back(pp);
- for(auto pp: p.second) res2.push_back(pp);
- for(auto pp: p.second) res3.push_back(pp);
- continue;
- }
- }
- }
- cout<<"YES\n";
- for(auto p: res1) cout<<p+1<<" ";
- cout<<'\n';
- for(auto p: res2) cout<<p+1<<" ";
- cout<<'\n';
- for(auto p: res3) cout<<p+1<<" ";
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét