EF Java题解，代码已去除冗余~~~

E 构造矩形

构造矩形的时候，分两种情况，要么以x轴为长边，要么以x轴为宽边；对于情况一（假设当前位置的横坐标为a[i]），需要的是使得a[i]-a[j]>=k 且 a[i]-a[j]-k<=m的所有前置边a[j]，而对于情况二，需要的是使得a[i]-a[j]+k<=m的所有前置边a[j]，分别维护前缀和以及有序映射即可快速求得答案，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        TreeMap<Integer,Integer> map=new TreeMap<>();
        long ans=0,pre[]=new long[n+5];
        for(int i=1;i<=n;i++){
            int a=sc.nextInt();
            //x轴为底边：
            Integer l=map.higherKey(a-k-m-1),r=map.lowerKey(a-k);
            if(l!=null&&r!=null){
                l=map.get(l);
                r=map.get(r);
                ans+=pre[r]-pre[l-1]+(long)(r-l+1)*(m-a+k+1);
            }
            //y轴为底边：
            l=map.higherKey(a+k-m-1);
            if(l!=null){
                l=map.get(l);
                ans+=pre[i-1]-pre[l-1]+(long)(i-l)*(m-a-k+1);
            }
            map.put(a,i);
            pre[i]=pre[i-1]+a;
        }
        System.out.println(ans);
    }
}

F 最快相同

题目中所述的操作等同于，每次选择n-k个数增加1，求最小的操作次数，需要找到最小的可以使得数组sum整除的n的最少次数p∈[0,n-1]，之后次数需要在p的基础上增加gcd(n,n-k)的最小非负整数倍，使得数组平均值不小于数组最大值，且对于数组最小值的增加次数不能大于操作次数，二分即可，事假复杂度O(n+logC),C==6e18

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=n-sc.nextInt(),max=0,min=(int)2e9;
        long sum=0;
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            sum+=a;
            max=Math.max(max,a);
            min=Math.min(min,a);
        }
        if(k==0){
            System.out.println(max==min?0:-1);
        }
        else{
            //先找到最少加k的次数，使得sum%n==0
            int p=0;
            while(p<n&&(sum+(long)p*k)%n!=0){
                p++;
            }
            if(p==n){
                System.out.println(-1);
            }
            else{
                long inc=n/gcd(k,n),l=0,r=(long)(8e18/inc/k);
                //增加的次数可以表示为num=p+inc*w，w∈N
                //(sum+k*num)/n>=max 且 (sum+k*num)/n-num<=min
                while(l<r){
                    long mid=(l+r)>>1;
                    if(check(max,min,sum,p+inc*mid,k,n)){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                    if(l==r-1){
                        if(check(max,min,sum,p+inc*l,k,n)){
                            r=l;
                        }
                        break;
                    }
                }
                System.out.println(p+inc*r);
            }
        }
    }
    static boolean check(long max,long min,long sum,long num,long k,long n){
        return (sum+k*num)/(double)n>=max&&(sum+k*num)/(double)n<=min+num;
    }
    static long gcd(long a,long b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}