fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5. import java.util.Scanner;
  6. import java.util.StringTokenizer;
  7.  
  8. class Solution {
  9.  
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         int t = sc.nextInt();
  13.         StringBuilder output = new StringBuilder();
  14.         while (t-- > 0) {
  15.             solve(sc, output);
  16.         }
  17.         System.out.print(output);
  18.     }
  19.  
  20.     private static void solve(Scanner sc, StringBuilder output) {
  21.         int n = sc.nextInt();
  22.         long c = sc.nextLong();
  23.  
  24.         long[] a = new long[n];
  25.         long totalSum = 0;
  26.         for (int i = 0; i < n; i++) {
  27.             a[i] = sc.nextLong();
  28.             totalSum += a[i];
  29.         }
  30.  
  31.         if (n <= 1) {
  32.             output.append(n).append("\n");
  33.             return;
  34.         }
  35.  
  36.         long[] rest = new long[n - 1];
  37.         for (int i = 0; i < n - 1; i++) {
  38.             rest[i] = a[i + 1];
  39.         }
  40.         Arrays.sort(rest);
  41.  
  42.         int answer = 0;
  43.  
  44.         for (int k = 1; k < n; k++) {
  45.             long sum_of_k_smallest = 0;
  46.             for (int j = 0; j < k; j++) {
  47.                 sum_of_k_smallest += rest[j];
  48.             }
  49.             long product1 = (totalSum - sum_of_k_smallest) * sum_of_k_smallest;
  50.  
  51.             long sum_of_k_largest = 0;
  52.             for (int j = 0; j < k; j++) {
  53.                 sum_of_k_largest += rest[rest.length - 1 - j];
  54.             }
  55.             long product2 = (totalSum - sum_of_k_largest) * sum_of_k_largest;
  56.  
  57.             long minProduct = Math.min(product1, product2);
  58.  
  59.             if (minProduct <= c) {
  60.                 answer = k;
  61.             }
  62.         }
  63.  
  64.         output.append(n - answer).append("\n");
  65.     }
  66. }
  67.  
Success #stdin #stdout 0.12s 56692KB
comments (?)
stdin
copy 
4
3 1000000000000000000
2000000 4000000 5000000
4 150
100 1 1 1
6 1275
35 15 10 25 10 5
6 400
35 15 10 25 10 5
stdout
copy 
1
3
4
6
https://ideone.com/Cwtdma
language:
Java (HotSpot 12)
created:
4 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!