Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- int main(){
- // freopen("input.inp","r",stdin);
- // freopen("output.out","w",stdout);
- string s;
- cin>>s;
- ll k;
- cin>>k;
- ll tmp=0;
- ll dem=0;
- while(k&&dem<=100){
- dem++;
- if(tmp==s.size()) tmp=0;
- char c = s[tmp];
- ll vt;
- ll dau=0;
- ll gg=tmp+k+1;
- ll ggg=s.size();
- for(ll i=tmp;i<min(gg,ggg);i++){
- if(s[i]>c){c=s[i];vt=i;dau=1;}
- }
- if(dau==1){
- for(ll i=vt;i>tmp;i--) swap(s[i],s[i-1]);
- k=k-(vt-tmp);
- }
- tmp++;
- }
- cout<<s;
- }
Không có nhận xét nào:
Đăng nhận xét