Thứ Bảy, 7 tháng 11, 2020

Thay đổi hai kí tự kề nhau không quá k lân để được số lớn nhất

 Đề bài: $\href{https://codeforces.com/problemset/problem/435/B}{đây}$

Tóm tắt: Cho số s và số nguyên $k$. In ra số lớn nhất có thể sau khi thực hiện không quá k phép toán đổi hai kí tự kề nhau.

Lời giải:

+ Ứng với mỗi phần tử trong s, ta sẽ kiểm tra k phần tử kế tiếp, rồi tìm phần tử lớn nhất, sau đó thay thế cho kí tự đang xét và giảm giá trị của k tương ứng !

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. // freopen("input.inp","r",stdin);
  6. // freopen("output.out","w",stdout);
  7. string s;
  8. cin>>s;
  9. ll k;
  10. cin>>k;
  11. ll tmp=0;
  12. ll dem=0;
  13. while(k&&dem<=100){
  14. dem++;
  15. if(tmp==s.size()) tmp=0;
  16. char c = s[tmp];
  17. ll vt;
  18. ll dau=0;
  19. ll gg=tmp+k+1;
  20. ll ggg=s.size();
  21. for(ll i=tmp;i<min(gg,ggg);i++){
  22. if(s[i]>c){c=s[i];vt=i;dau=1;}
  23. }
  24. if(dau==1){
  25. for(ll i=vt;i>tmp;i--) swap(s[i],s[i-1]);
  26. k=k-(vt-tmp);
  27. }
  28. tmp++;
  29. }
  30. cout<<s;
  31. }

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ự...