2015-7-28 美团面试 算法题

算法 面试

面试的时候想复杂了。。。
数据范围： $1\le a\le 10^18$, $0 \le k \le 100$,
对于每一个位的处理，只要找到能在剩余步数中一直交换到当前位且大于当前位数值的最大数，按照题意逐个交换即可，记得把k减去相应的步数；
因为k很小而且a的位数也很小，时间上可以承受；

#include <stdio.h>
#include <stdlib.h>
int k, len;
char a[20];
void input()
{
    int i;
    scanf("%s", a);
    scanf("%d", &k);
    len = strlen(a);
    for(i = 0; i < len; i++)
        a[i] -= '0';
}
void output()
{
    int i;
    for(i = 0; i < len; i++){
        printf("%d", a[i]);
    }
}
void work(int l)
{
    int i, j, mx = -1, mxi = 0, tmp;
    for(i = l + 1; i < l + k + 1 && i < len; i++){  //贪心找符合条件的最大数
        if(a[i] > a[l] && a[i] > mx)
            mx =a[i], mxi = i;
    }
    if(mx != -1){
        for(j = mxi; j > l; j--){   //交换相邻的数
            tmp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = tmp;
        }
        k -= mxi - l;  //更新剩余步数
    }
    return;
}
int main()
{
    int l = 0;
    input();
    while(k && l < len){
        work(l++);  //还剩步数的情况下处理每一位
    }
    output();
    return 0;
}