CF1278B-A and B-(简单数学)

starletkiss 2019-12-20

https://vjudge.net/problem/CodeForces-1278B

题意:给两个数a和b,有一种操作:第i次操作任选其中一个数加或减i;如第1次操作可以任选其中一个数加1或减1,第2次操作可以任选其中一个数加2或减2。问至少几次操作后使得a和b相等。

思路:

刚看到这道题一时半会没想出来,但难度只是B,理论上应该能做出来,手写列举两数之差cha

0=0

1=1

2=1+3-2

3=1+2

4=2+3-1

5=1+2+3+4-5

6=1+2+3

7=1+2+3+5-4

...

猜测:如果需要减只需要减一个数

初始化一个前缀和数组sum[i],前缀和不超过109;如果(sum[i]-cha)%2==0则可以得到最小次数i。结果真的AC了。。。记录一下这道简单数学题。

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main{
    
    public static void main(String []args) {
        Scanner scan=new Scanner(System.in);
        int t=scan.nextInt();
        int [] sum=new int[50000];
        for(int i=1;i<50000;i++)
            sum[i]=sum[i-1]+i;
        
        while(t!=0) {
            t--;
            int a=scan.nextInt();
            int b=scan.nextInt();
            int cha=0;
            if(a>b)
                cha=a-b;
            else 
                cha=b-a;
            
            for(int i=0;i<=sum[i];i++)
            {
                if((sum[i]-cha)%2==0 && (sum[i]-cha)>=0 ) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
 
}

相关推荐

seasongirl / 0评论 2020-06-05