题目描述

仅供参考，供个人复习时使用
同时参考借鉴了 抽象带师的题解 抽象带师的题解

算法

显然，涉及到了区间和最小值的问题，采用前缀和+二分

但是困难的是怎么用这个二分和前缀和

第一步就是这个式子，没理解那个1是怎么回事
应该是这样的，当假设的W大于每一个物品的重量的时候个数加1

然后知道所用的算法是二分，怎么用二分，二分的目的肯定是找出一个w
W增大Y减小，也就是说数据呈现一个单调递减的走势

那么边界怎么确定呢？（我好像一直不会确定边界）

然后就是对于区间边界的问题，也就是最后结果的取值
怎么样的取值才算是一个最接近s的值呢？
根据二分的划分的不同而有所不同
1.L L+1
2.L L-1

一部分小于等于s,一部分大于s

package day;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import javax.swing.text.StyledEditorKit.ForegroundAction;

public class 聪明的质监员 {

    /**
     * @param args
     * @throws IOException 
     */
    static int N=200000+10;
    static int n,m;
    static long s;
    static int w[]=new int [N];
    static int v[]=new int [N];
    static int L[]=new int [N];
    static int R[]=new int [N];
    static long  sum[]=new long [N];
    static int cnt[]=new int [N];

    public static long   check(int mid) {

        for(int i=1;i<=n;i++){
            if(w[i] >= mid) {
                sum[i]=sum[i-1]+v[i];
                cnt[i]=cnt[i-1]+1;
            }else {
                sum[i]=sum[i-1];
                cnt[i]=cnt[i-1];
            }
        }
        long res=0;
        for(int i=1;i<=m;i++){
            res=res+(long)(sum[R[i]]-sum[L[i]-1])*(cnt[R[i]]-cnt[L[i]-1]);
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");

        n=Integer.parseInt(p[0]);
        m=Integer.parseInt(p[1]);
        s=Long.parseLong(p[2]);

        for(int i=1;i<=n;i++){
            p=bufferedReader.readLine().split(" ");
            w[i]=Integer.parseInt(p[0]);
            v[i]=Integer.parseInt(p[1]);
        }

        for(int i=1;i<=m;i++){
            p=bufferedReader.readLine().split(" ");
            L[i]=Integer.parseInt(p[0]);
            R[i]=Integer.parseInt(p[1]);
        }

        int l=0;
        int r=(int) (1e6+1);
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)>s ){
                l=mid+1;
            }else
            {
                r=mid;
            }
        }
        long ans1=Math.abs(check(l)-s);
        long ans2=Math.abs(check(r-1)-s);

        System.out.println(Math.min(ans1, ans2));
    }

}

一部分大于等于s，一部分小于s

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import javax.swing.text.StyledEditorKit.ForegroundAction;

public class  Main  {

    /**
     * @param args
     * @throws IOException 
     */
    static int N=200000+10;
    static int n,m;
    static long s;
    static int w[]=new int [N];
    static int v[]=new int [N];
    static int L[]=new int [N];
    static int R[]=new int [N];
    static long  sum[]=new long [N];
    static int cnt[]=new int [N];

    public static long   check(int mid) {

        for(int i=1;i<=n;i++){
            if(w[i] >= mid) {
                sum[i]=sum[i-1]+v[i];
                cnt[i]=cnt[i-1]+1;
            }else {
                sum[i]=sum[i-1];
                cnt[i]=cnt[i-1];
            }
        }
        long res=0;
        for(int i=1;i<=m;i++){
            res=res+(long)(sum[R[i]]-sum[L[i]-1])*(cnt[R[i]]-cnt[L[i]-1]);
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");

        n=Integer.parseInt(p[0]);
        m=Integer.parseInt(p[1]);
        s=Long.parseLong(p[2]);

        for(int i=1;i<=n;i++){
            p=bufferedReader.readLine().split(" ");
            w[i]=Integer.parseInt(p[0]);
            v[i]=Integer.parseInt(p[1]);
        }

        for(int i=1;i<=m;i++){
            p=bufferedReader.readLine().split(" ");
            L[i]=Integer.parseInt(p[0]);
            R[i]=Integer.parseInt(p[1]);
        }

        int l=0;
        int r=(int) (1e6+1);
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid) >=s ){
                l=mid;
            }else
            {
                r=mid-1;
            }
        }
        long ans1=Math.abs(check(l)-s);
        long ans2=Math.abs(check(r+1)-s);

        System.out.println(Math.min(ans1, ans2));
    }

}