253B - Physics Practical - CodeForces Solution

binary search dp sortings two pointers *1400

Please click on ads to support us..

C++ Code: 

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

int main() {
 	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
		
	ll n;
	cin >> n;
	
	vector<ll> v(n,0);
	for(ll i=0;i<n;i++)
        cin >> v[i];
	
	ll i=0,j=0,maxi=v[0],mini = v[0],ans=0;
	sort(v.begin(),v.end());
	
	while(j<n)
	{
		maxi = v[j];
		mini = v[i];
		
		while(i<=j && maxi>2*mini)
		{			i++;
			maxi = v[j];
			mini = v[i];
		}
		ans = max(ans,(ll)j-i+1);
		j++;
	}
	
	cout << n-ans << endl;
	return 0;
}


Comments

Submit
1 Comments
  • 11/4/2023 18:45 - Africa/Cairo

#include <bits/stdc++.h>
#define endl '\n'
#define Fast ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;


int main() {
    Fast;
    int n;cin>>n;
    vector<int>v(n);
    for (int i =0 ;i < n ;i++)
    {
        cin>>v[i];
    }
    sort (v.begin(),v.end());
    // binary search by searching on mid
    if (v[n-1]-v[0]<=2) cout<<0;
    else
    {
        int lo = 0, hi = v.size() - 1, mid;
        while (lo <= hi)
        {
             mid = (lo + hi) / 2;
             if (hi-v[0]<=2) break;
             if (v[mid]-v[0]>2) hi =mid-1;
             else if (v[mid]-v[0]<=2) lo =mid+1;


        }
        cout<<v.size()-(hi-1);
    }
        return 0;
}

More Questions

Duration
Birthday Party
e-maze-in
Bricks Game
Char Sum
Two Strings
Anagrams
Prime Number
Lexical Sorting Reloaded
1514A - Perfectly Imperfect Array
580A- Kefa and First Steps
1472B- Fair Division
996A - Hit the Lottery
MSNSADM1 Football
MATCHES Playing with Matches
HRDSEQ Hard Sequence
DRCHEF Doctor Chef
559. Maximum Depth of N-ary Tree
821. Shortest Distance to a Character
1441. Build an Array With Stack Operations
1356. Sort Integers by The Number of 1 Bits
922. Sort Array By Parity II
344. Reverse String
1047. Remove All Adjacent Duplicates In String
977. Squares of a Sorted Array
852. Peak Index in a Mountain Array
461. Hamming Distance
1748. Sum of Unique Elements
897. Increasing Order Search Tree
905. Sort Array By Parity