fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone {
  6.     public static void main (String[] args) throws java.lang.Exception {
  7.         Scanner in = new Scanner(System.in);
  8.         int n = in.nextInt();
  9.         int q = in.nextInt();
  10.  
  11.         long b[] = new long[n+1];
  12.         long query[][] = new long[q+1][3];
  13.         long t = 0;
  14.         for(int i=1;i<=n;i++){
  15.             b[i] = in.nextLong();
  16.             t = t + b[i];
  17.         }
  18.  
  19.          Arrays.sort(b); 
  20.  
  21.         for(int j=1;j<=q;j++){
  22.             query[j][1] = in.nextLong();
  23.             query[j][2] = in.nextLong();
  24.         }
  25.  
  26.         for(int i=1;i<=q;i++){
  27.             long x1 = query[i][1];
  28.             long y1 = query[i][2];
  29.             long cost = Long.MAX_VALUE;
  30.  
  31.             int pos = bs(b,x1);//Binary Search for the lowest bound
  32.  
  33.        if(pos<n){
  34.        	long bj = b[pos];
  35.        	long p1 = Math.max(0,x1-bj);
  36.        	long p2 = Math.max(0,y1-(t-bj));
  37.        	cost = Math.min(cost,p1+p2);
  38.        }
  39.  
  40.        if(pos>0){
  41.        	long bj = b[pos-1];
  42.        	long p1 = Math.max(0,x1-bj);
  43.        	long p2 = Math.max(0,y1-(t-bj));
  44.        	cost = Math.min(cost,p1+p2);
  45.        }
  46.  
  47.       System.out.println(cost);
  48.         }
  49. }
  50.         public static int bs(long[] arr,long x){
  51.         	int low =0;
  52.         	int high = arr.length-1;
  53.         	int pos = arr.length;
  54.         	while(low<=high){
  55.         		int mid = (low+high)/2;
  56.         		if(arr[mid] >=x){
  57.         			pos = mid;
  58.         			high = mid-1;
  59.         		}
  60.         		else{
  61.         			low = mid+1;
  62.         		}
  63.         	}
  64.         	return pos;
  65.         }
  66.  
  67. }
  68.  
Success #stdin #stdout 0.18s 56600KB
comments (?)
stdin
copy 
5
2 5 9 12 20
3
15 25
25 58
7 41
stdout
copy 
3
34
https://ideone.com/QDXguj
language:
Java (HotSpot 12)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!