抛砖引玉： 6218-牛客编程巅峰赛S1赛季第1场 - 青铜&白银局

试着做了一下，给出我的代码，希望能抛砖引玉。
题目链接 牛客编程巅峰赛S1赛季第1场 - 青铜&白银局

题A

char* change(char* s ) {
    // write code here
    long len = strlen(s), newLen = 0;
    char* newstr = (char*)malloc((len+1)*sizeof(char));

    for(int i = 0; i<len; i++){
        if('a' != s[i])
            newstr[newLen++] = s[i];
    }
    for(int i = newLen; i<len; i++){
        newstr[newLen++] = 'a';
    }
    newstr[len] = '\0';
    return newstr;
}

题B

原本想用递归暴力求解。其中当n比m大的时候，直接返回差值n-m。就是下面这个：

int solve(int n, int m) {
    // write code here
    if (n < m) {
        int a = solve(n * n, m) + 1;
        int b = solve(n + 1, m) + 1;
        int c = solve(n - 1, m) + 1;
        return a < min(b,c) ? a : min(b,c);
    }
    else {
        return n - m;
    }
}

但这太暴力了，系统无法接受这么粗鲁的对待，所以换了个正常的求解思路（当然也可以继续此思路，利用队列，将递归转化为动态规划）：

• 题设条件下，设到达m的最快路径为 { M_i }：

  

• 我们要做的就是寻找到, 使得，此时操作数为：

  

• 由于对n操作的结果均为整数，需要将进行四舍五入得 { a_i }：

  

• 舍入时存在误差，每一步的误差，此时的操作数：

  

对应代码如下:

int solve(int n, int m ) {
    // 预处理
    if(m <= n)
        return n-m;

    int sqCnt = 1, a = round(sqrt(m)), errCnt = abs(m - root * root);
    int oldCnt = m - n, newCnt = abs(root - n) + errCnt + sqCnt;
    while (oldCnt > newCnt) {
        // 平方步数计算
        int rootTmp = round(sqrt(root));
        errCnt += abs(root - rootTmp * rootTmp);    // 误差
        root = rootTmp;     // 整数根 a_i
        sqCnt++;            // 开方次数

        // 新值计算
        oldCnt = newCnt;
        newCnt = abs(root - n) + errCnt + sqCnt;
    }
    return oldCnt;
}

题C

动态规划求解

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
int buf[2020][2020]; // 所占字节数太多，所以放在堆中

int minCost(int breadNum, int beverageNum, int** packageSum, int packageSumRowLen, int* packageSumColLen ) {
    // 初始化
    memset(buf, 0x7f, sizeof(buf));
    buf[0][0] = 0;

    for(int row=0; row<packageSumRowLen; row++){
        int brd = packageSum[i*3 +0], drk = packageSum[i*3 +1], cost = packageSum[i*3 +2];
        for(int i = breadNum; i >= 0; i--){
            for(int j = beverageNum; j >= 0; j--){
                buf[i][j] = min(buf[i][j], buf[max(i-brd, 0)][max(j-drk, 0)]+cost);
            }
        }
    }

    return buf[breadNum][beverageNum];
}