fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     // Binary search: find last index where value <= target
  6.     static int findLastSmallerOrEqual(long[] arr, long target) {
  7.         int left = 0, right = arr.length - 1;
  8.         int index = -1;
  9.  
  10.         while (left <= right) {
  11.             int mid = (left + right) / 2;
  12.  
  13.             if (arr[mid] <= target) {
  14.                 index = mid;        // valid index
  15.                 left = mid + 1;     // move right to find last
  16.             } else {
  17.                 right = mid - 1;
  18.             }
  19.         }
  20.         return index;
  21.     }
  22.  
  23.     public static void main(String[] args) {
  24.  
  25.         Scanner sc = new Scanner(System.in);
  26.  
  27.         // Size of array
  28.         int n = sc.nextInt();
  29.  
  30.         // Input array
  31.         long[] numbers = new long[n];
  32.         for (int i = 0; i < n; i++) {
  33.             numbers[i] = sc.nextLong();
  34.         }
  35.  
  36.         // Sort array
  37.         Arrays.sort(numbers);
  38.  
  39.         // Prefix sum
  40.         long[] prefixSum = new long[n + 1];
  41.         for (int i = 1; i <= n; i++) {
  42.             prefixSum[i] = prefixSum[i - 1] + numbers[i - 1];
  43.         }
  44.  
  45.         long totalSum = prefixSum[n];
  46.  
  47.         // Number of queries
  48.         int queries = sc.nextInt();
  49.  
  50.         // Process each query
  51.         for (int q = 0; q < queries; q++) {
  52.  
  53.             long target = sc.nextLong();
  54.  
  55.             // Binary search index
  56.             int lastIndex = findLastSmallerOrEqual(numbers, target);
  57.  
  58.             // Count of elements <= target
  59.             int leftCount = lastIndex + 1;
  60.  
  61.             // Operations to increase smaller elements
  62.             long leftOps = target * leftCount - prefixSum[leftCount];
  63.  
  64.             // Operations to decrease bigger elements
  65.             long rightOps = (totalSum - prefixSum[leftCount]) 
  66.                             - target * (n - leftCount);
  67.  
  68.             // Total operations
  69.             long totalOperations = leftOps + rightOps;
  70.  
  71.             System.out.println(totalOperations);
  72.         }
  73.  
  74.         sc.close();
  75.     }
  76. }
  77.  
  78.  
Success #stdin #stdout 0.18s 54504KB
comments (?)
stdin
copy 
5
1 3 5 7 9
3
6
4
10
stdout
copy 
13
13
25
https://ideone.com/b0nQFJ
language:
Java (HotSpot 12)
created:
10 hours 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!