牛客编程巅峰赛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]++; } }