Блог пользователя anushkanocoding

TESTCASE DOUBT
Автор anushkanocoding, история, 4 месяца назад, По-английски

import java.util.*; public class balanced { public static void main(String[]args){ java.util.Scanner sc=new java.util.Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;i++){ int n=sc.nextInt(); int k=sc.nextInt(); int []arr=new int[n]; for(int j=0;j<arr.length;j++){ arr[j]=sc.nextInt(); }

int ops=0;
        Arrays.sort(arr);
        int a=0;
        int b=1;
        while(b<arr.length){ 
            if(arr[b]-arr[b-1]>k){
                int leftNums=b-a;
                int rightNums=arr.length-b;

                if(leftNums<rightNums){
                    a=b;
                    ops+=leftNums;
                }else if(leftNums>=rightNums){
                    ops+=rightNums;
                    break;
                }
            }
            b++;
        }
        System.out.println(ops);
    }
}

} For Question 1850D-BALANCED ROUND Can anyone please tell me what the problem is with the code? It Fails on TestCase 409 i cant see the particular testcase (also can we actually see particular testcases? if not, how is one supposed to know which testcase is wrong?

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Logic is pretty simple for this question. take in array of length 'n', sort the array, find length 'len' of the longest subarray without violating the condition of 'difference <=k' and you got your answer 'n-len'.

here is the code


#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; 
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> v(n);
        
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        
        sort(v.begin(), v.end());
        
        int maxLen = 0, currLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (v[i] - v[i-1] <= k) {
                currLen++;
            } else {
                maxLen = max(maxLen, currLen);
                currLen = 1;
            }
        }
        
        maxLen = max(maxLen, currLen);
        
        cout << n - maxLen << endl;
    }

    return 0;
}

time complexity is O(nlogn) due to sorting.

→ Ответить