牛客编程巅峰赛S1第8场-青铜&白银 第三题

牛牛构造等差数列

https://ac.nowcoder.com/acm/contest/6776/C

用回溯算法做只过了60%, 不知道错在哪了,求大佬们赐教~

public class Solution {
    /**
     * 返回最少多少次操作后能使这几个数变成一个等差数列,如果完全不能构造成功,就返回-1
     * @param n int整型 代表一共有n个数字
     * @param b int整型一维数组 代表这n个数字的大小
     * @return int整型
     */
    private int ans = Integer.MAX_VALUE;
    public int solve (int n, int[] b) {
        // 回溯算法
        if(b.length == 1 || b.length == 2) return 0;
        dfs(b, 0, 0);
        return ans == Integer.MAX_VALUE?-1:ans;
    }

    public void dfs(int[] b , int ind, int op) {
        //check
        int i;
        int gc = b[0] - b[1];  // 公差
        for(i = 0; i < b.length - 1; i++) {
            if(b[i] - b[i+1] != gc) {
                if(i < ind - 1) return;
                break;
            }
        }
        // 满足等差数列
        if(i >= b.length - 1) {
            ans = Math.min(ans, op);
            return;
        }
        // 剪枝
        if(ans <= op) {
            return;
        }
        if(ind >= b.length - 1) return;
        //no operation
        dfs(b, ind+1, op);
        //plus one
        b[ind]++;
        dfs(b, ind+1, op+1);
        b[ind]--;
        //minus one
        b[ind]--;
        dfs(b, ind+1, op+1);
        b[ind]++;
    }
}
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务