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);

         }

     }

 }

巴特西

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

最新文章

热门文章