P1314 [NOIP2011 提高组] 聪明的质监员JAVA

[NOIP2011 提高组] 聪明的质监员 - 洛谷

当w取最小为0时yi最大,当w取最大时yi最小

所以可以使用二分答案,当yis,则w小了

并且在求yi时多次求区间和 需要用到前缀和

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

class  Main{
    static int[][] stone;
    static int[][] section;
    static int n,m;
    static long s;
    public static void main(String[] args) throws IOException {
        StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        cin.nextToken();
        n = (int)cin.nval;
        cin.nextToken();
        m = (int)cin.nval;
        cin.nextToken();
        s = (long)cin.nval;
        int max=0;
        stone = new int[n][2];
        for(int i=0;imax)
                max = stone[i][0];
            cin.nextToken();
            stone[i][1] = (int)cin.nval;
        }
        section = new int[m][2];
        for(int i=0;i>1;
            long x = sum(mid);
            if(x==s){
                res = mid;
                break;
            }
            else if(x