乐视——蚂蚁跳跃算法？只能通过67%？
乐视——蚂蚁跳跃算法，一开始用的贪心算法，后来发现只能a 17%，换了个想法。就是x = 1 2 3 4 5...n
在其中加上+和-符号，这样就可以转化为一个一元二次方程组，即为n^2 + n - 2x =
0。用公式法求解，并尝试下n和n+1，从而去发现与目标差距。最后没有尝试n-1和n+2，是不是取整的时候有问题？还是啥？求大神解法。。
底下是我的代码
import java.util.Scanner;
public class Main {
public static long myCore(long maxNLeft, long a){
long curSum = maxNLeft * (maxNLeft + 1) / 2;
long leftResult = maxNLeft;
// System.out.println("curSum:" + curSum);
if(curSum == a){
return maxNLeft;
}
else if(curSum > a){
if((curSum - a) % 2 == 0){
leftResult += 0;
}
else{
leftResult += 2;
}
}
else{
leftResult += (a - curSum) * 2;
}
return leftResult;
}
public static long myProcess(long a){
a = Math.abs(a);
if(a == 0) return 0;
long maxNLeft = (long) ((-1 + Math.sqrt(1 + 8 * a)) / 2.0);
long maxNRight = maxNLeft + 1;
long maxNLeft0 = maxNLeft - 1;
long maxNRight0 = maxNLeft + 2;
long leftResult = myCore(maxNLeft, a);
long rightResult = myCore(maxNRight, a);
long leftResult0 = myCore(maxNLeft0, a);
long rightResult0 = myCore(maxNRight0, a);
return Math.min(Math.min(leftResult, rightResult), Math.min(leftResult0, rightResult0));
}
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
long a;
while (cin.hasNextLong()) {
a = cin.nextLong();
System.out.println(myProcess(a));
}
}
}
投递哔哩哔哩等公司6个岗位 >
