题目解析

看公式就看了半天，总结来说就是，自己设定一个W，用区域内比这个W重的物品数量*这些物品的价值之和=检验值。 求检验值与标准值之间最小的差值。

通过简单的分析可以得出，当我们选定的W约小的时候，所求的Y越大，相反当W越大的时候，Y就越小，所以有单调性，适用于二分查找。

于是有以下代码：

import java.util.*;
public class Main
{
    public static int check(int W,int[][] weights,int [][]arr)
    {
        int  n=weights.length;
        int m=arr.length;
        int Y=0;
        for(int i=0;i<m;i++)
        {
            int num=0;
            int value=0;
            for(int j=arr[i][0];j<=arr[i][1];j++)
            {
                if(weights[j][0]>=W)
                {
                    num++;
                    value+=weights[j][1];
                }
            }
            Y+=num*value;
        }
        return Y;
    }

    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int s=sc.nextInt();
        int [][]kuang=new int[n+1][2];
        int [][]qujian=new int[m][2];
        int max=0;
        for(int i=1;i<=n;i++)
        {
            kuang[i][0]=sc.nextInt();
            kuang[i][1]=sc.nextInt();
            max=Math.max(max,kuang[i][0]);
            sc.nextLine();
        }
        for(int i=0;i<m;i++)
        {
            qujian[i][0]=sc.nextInt();
            qujian[i][1]=sc.nextInt();
            sc.nextLine();
        }
        int left=0;
        int right=max+1;
        int res=0;
        while(left<=right)
        {
            int mid=(left+right)>>>1;
            int cha=check(mid,kuang,qujian);
            if(cha<s) {
                right=mid-1;

            }
            else {
                left=mid+1;
            }
        }
        int cha=Math.min(Math.abs(s-check(right+1,kuang,qujian)),Math.abs(s-check(right,kuang,qujian)));
        System.out.println(cha);
    }
}

出现了答案错误，一定要注意审题！！！ S的范围已经严重越界了，不能用int进行数据存储。

将所有可能越界的数变为long后：

于是处理超时，还是对于题目信息的提取不到位：

区间是可能相互重叠的，因此涉及到了大于W的个数以及价值的重复计算，考虑使用前缀和来避免重复计算，不重叠时，可能不计算前缀和的速度会更快，此时重叠，因此，修改代码为：

import java.util.*;
public class Main
{
    public static long check(int W,int[][] weights,int [][]arr)
    {
        int  n=weights.length;
        int m=arr.length;
        long Y=0;//记录标准差
        long []sum=new long[n];//记录前n个重量大于W的价值和
        long []count=new long[n];//记录前n个重量大于W的个数
        for(int i=1;i<n;i++)
        {
            if(weights[i][0]>=W)
            {
                sum[i]=sum[i-1]+weights[i][1];
                count[i]=count[i-1]+1;
            }
            else {
                sum[i]=sum[i-1];
                count[i]=count[i-1];
            }
        }
        for(int i=1;i<m;i++)
        {
            Y+=(sum[arr[i][1]]-sum[arr[i][0]-1]) //范围内大于W的价值
                    *(count[arr[i][1]]-count[arr[i][0]-1]);//范围大于W的个数
        }
        return Y;
    }

    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        long s=sc.nextLong();
        int [][]kuang=new int[n+1][2];
        int [][]qujian=new int[m+1][2];
        int max=0;
        for(int i=1;i<=n;i++)
        {
            kuang[i][0]=sc.nextInt();
            kuang[i][1]=sc.nextInt();
            max=Math.max(max,kuang[i][0]);
            sc.nextLine();
        }
        for(int i=1;i<=m;i++)
        {
            qujian[i][0]=sc.nextInt();
            qujian[i][1]=sc.nextInt();
            sc.nextLine();
        }
        int left=0;
        int right=max+1;
        int res=0;
        while(left<=right)
        {
            int mid=(left+right)>>>1;
            long cha=check(mid,kuang,qujian);
            if(cha<s) {
                right=mid-1;

            }
            else {
                left=mid+1;
            }
        }
        long cha=Math.min(Math.abs(s-check(right+1,kuang,qujian)),Math.abs(s-check(right,kuang,qujian)));
        System.out.println(cha);
    }
}