Thứ Sáu, 20 tháng 11, 2020

Bài toán in ra chỉ số thỏa mãn dãy đã cho không giảm

 Đề 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:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. map<ll,vector<ll> > mt;
  5. vector<ll> res1,res2,res3;
  6. int main(){
  7. ll n;
  8. cin>>n;
  9. ll a[n];
  10. ll i;
  11. for(i=0;i<n;i++) {
  12. cin>>a[i];
  13. mt[a[i]].push_back(i);
  14. }
  15. ll dau=0,cnt=0;
  16. // for(auto p: mt){
  17. // cout<<p.first<<"---";
  18. // for(auto k: p.second) cout<<k<<" ";
  19. // cout<<'\n';
  20. // }
  21. for(auto p: mt){
  22. if(p.second.size()>=3) {dau=2;break;}
  23. else if(p.second.size()==2) cnt++;
  24. if(cnt==2) {dau=1;break;}
  25. }
  26. if(dau==0) {cout<<"NO"; return 0;}
  27. if(dau==2){
  28. for(auto p: mt){
  29. if(p.second.size()<=2)
  30. for(auto k: p.second) {
  31. res1.push_back(k);
  32. res2.push_back(k);
  33. res3.push_back(k);
  34. }
  35. if(p.second.size()>=3){
  36. sort(p.second.begin(),p.second.end());
  37. for(auto pp: p.second) res1.push_back(pp);
  38. next_permutation(p.second.begin(),p.second.end());
  39. for(auto pp: p.second) res2.push_back(pp);
  40. next_permutation(p.second.begin(),p.second.end());
  41. for(auto pp: p.second) res3.push_back(pp);
  42. }
  43. }
  44. }
  45. else if(dau==1){
  46. for(auto p: mt){
  47. if(p.second.size()<=1)
  48. for(auto k: p.second) {
  49. res1.push_back(k);
  50. res2.push_back(k);
  51. res3.push_back(k);
  52. }
  53. if(p.second.size()>=2&&cnt==2){
  54. sort(p.second.begin(),p.second.end());
  55. for(auto pp: p.second) res1.push_back(pp);
  56. for(auto pp: p.second) res2.push_back(pp);
  57. next_permutation(p.second.begin(),p.second.end());
  58. for(auto pp: p.second) res3.push_back(pp);
  59. cnt-=1;
  60. continue;
  61. }
  62. if(p.second.size()>=2&&cnt==1){
  63. sort(p.second.begin(),p.second.end());
  64. for(auto pp: p.second) res1.push_back(pp);
  65. next_permutation(p.second.begin(),p.second.end());
  66. for(auto pp: p.second) res2.push_back(pp);
  67. for(auto pp: p.second) res3.push_back(pp);
  68. cnt-=1;
  69. continue;
  70. }
  71. if(p.second.size()>=2&&cnt==0){
  72. for(auto pp: p.second) res1.push_back(pp);
  73. for(auto pp: p.second) res2.push_back(pp);
  74. for(auto pp: p.second) res3.push_back(pp);
  75. continue;
  76. }
  77. }
  78. }
  79. cout<<"YES\n";
  80. for(auto p: res1) cout<<p+1<<" ";
  81. cout<<'\n';
  82. for(auto p: res2) cout<<p+1<<" ";
  83. cout<<'\n';
  84. for(auto p: res3) cout<<p+1<<" ";
  85. return 0;
  86. }
  87.  

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...