UVa10025-The ? 1 ? 2 ? … ? n = k problem

分析：因为数字之间只有加减变换，所以-k和k是一样的，都可以当成整数来考虑，只要找到最小的n满足sum=n*(n+1)/2>=k；且sum和k同奇同偶即可，做法是用二分查找，然后在就近查找

因为1，2，3，4，5，6……的sum变化是奇奇偶偶奇奇偶偶奇奇偶偶……

程序：

 import java.math.BigInteger;
 import java.util.Scanner;
 public class Main {
     static long l,r,mid;
     public static long Binary(long k){
         l=0;r=100000;
         long ans=0;
         while(l<=r){
             mid=(l+r)/2;
             long sum=mid*(mid+1)/2;
             if(sum>=k){
                 ans=mid;
                 r=mid-1;
             }
             else{
                 l=mid+1;
             }
         }
         return ans;
     }
     public static long fun(long k){
         if(k==0)
             return 3;
         long ans=Binary(k);
         long sum=ans*(ans+1)/2;
         if(k%2!=0){
             for(long i=ans;i>=0;i--){
                 long s=i*(i+1)/2;
                 if(s<k)break;
                 if(s%2!=0)
                     return i;
             }
             for(long i=ans;;i++){
                 long s=i*(i+1)/2;
                 if(s%2!=0)
                     return i;
             }
         }
         else{
             for(long i=ans;i>=0;i--){
                 long s=i*(i+1)/2;
                 if(s<k)break;
                 if(s%2==0)
                     return i;
             }
             for(long i=ans;;i++){
                 long s=i*(i+1)/2;
                 if(s%2==0)
                     return i;
             }
         }
     }
     public static void main(String args[]){
         Scanner cin=new Scanner(System.in);
         int n;
         n=cin.nextInt();
         for(int i=0;i<n;i++){
             long k;
             k=cin.nextInt();
             if(k<0)
                 k=-k;
             long ans=fun(k);
             if(i!=0)
                 System.out.println();
             System.out.println(ans);
         }
     }
 }