1786C - Monsters (easy version) - CodeForces Solution


greedy sortings

Please click on ads to support us..

C++ Code:

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <sstream>
#include <iterator>
#include <map>
#include <unordered_set>
#include <bitset>
#include <utility>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//  
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
//#include <bits/stdc++.h>
//order_of_key (k)
//find_by_order(k)
//order_of_key (k) : Number of items strictly smaller than k .

//find_by_order(k) : K-th element in a set (counting from zero).
#define FAST                 \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);

using namespace std;
    set <unsigned long long> set1;
bool isPrime(long long  n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to n-1
    for (long long  i = 2; i <= n/2; i++)
        if (n % i == 0)
            return false;
 
    return true;
}
void vectorofPrimeFactors(int n) {
    if(n==1) {
        set1.insert(1);
        return;
    }
   while (n%2 == 0){
      set1.insert(2);
      n = n/2;
   }
   int stop=sqrt(n);
   for (int i = 2; i <= stop;  i++){
      while (n%i == 0){
         set1.insert(i);
         n = n/i;
      }
   }
   if (n > 2) {
   set1.insert(n);
   
   }
}
ll gcdarray(vector<ll>& a)
{
	int n = a.size();
	long long  ans = a[0];
	for (int i = 1; i < n; i++)
	{
		ans = __gcd(ans, a[i]);
	}
	return ans;
}
ll lcmarray(vector<ll>& a)
{
	int n = a.size();
	ll b = gcdarray(a);
	int ans = 1;
	for (int i = 0; i < n; i++)
	{
		ans *= a[i];
	}
	return ans / b;
}
unsigned long long combination(unsigned long long n,unsigned long long r) {
    if(n<r)
        return 0;
    if(n==1)
        return 1;
    if(r==1)
        return n;
    if(r==0)
        return 1;
    
    
    
    return combination(n-1,r)+combination(n-1,r-1);
}
long long per(long long n,long long r)
{
	if (r==1)
		return n;
	return n * per(n - 1,r-1);


}
long long fact(long long n)
{
	if (n <= 1)
		return 1;
	return n * fact(n - 1);
}
long long comb(long long n, long long r)
{
	if (n < r)
		return 0;
	if (n == 1)
		return 1;
	if (r == 0)
		return 1;
	if (r == 1)
		return n;
	
	return comb(n - 1, r-1) + comb(n - 1, r );

}
long long perm(long long n, long long r)
{
	return comb(n, r) * fact(r);
}
void sieve_of_eratosthenes(int &L, int &R)
{
    // Create a boolean array "prime[L..R]" and mark all entries as true, which means that all the numbers are initially considered as primes.
    
    // total  number of elements in the array would be R + 1
    bool prime[R + 1];
    memset(prime, true, sizeof(prime));
 
    // start looking with the smallest prime number, i.e L.
    
    for (int p = 2; p * p <= R; p++) {
        
        // if it is the next prime, then mark all its multiples as false, as they are composite and not prime.
        if (prime[p] == true) {
            
            for (int i = p * p; i <= R; i += p)
                prime[i] = false;
        }
}
}
void SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p greater than or
            // equal to the square of it numbers which are
            // multiple of p and are less than p^2 are
            // already been marked.
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Print all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << " ";
}
 

int main () {
      // FAST
      int t;
      cin>>t;
      while(t--) {
            long long  n;
            cin>>n;
            long long  array1[n];
            for(long long i=0;i<n;i++) {
                cin>>array1[i];
            }
            long long current;
            long long ans=0;
            sort(array1,array1+n);
            if(array1[0]!=1) {
                ans+=(array1[0]-1);
                array1[0]=(array1[0])-(array1[0]-1);
            }
            current=array1[0];
            for(long long i=1;i<n;i++) {
                if(array1[i]>current+1) 
                    ans+=(array1[i]-(current+1));
                 if(array1[i]==current)
                     continue;
                    else
                       current++;
            
            }
            cout<<(ans)<<"\n";
            
      }

}


Comments

Submit
0 Comments
More Questions

755C - PolandBall and Forest
456B - Fedya and Maths
376B - IOU
1623B - Game on Ranges
1118A - Water Buying
1462C - Unique Number
301A - Yaroslav and Sequence
38A - Army
38C - Blinds
1197A - DIY Wooden Ladder
1717D - Madoka and The Corruption Scheme
1296D - Fight with Monsters
729D - Sea Battle
788A - Functions again
1245B - Restricted RPS
1490D - Permutation Transformation
1087B - Div Times Mod
1213B - Bad Prices
1726B - Mainak and Interesting Sequence
1726D - Edge Split
1726C - Jatayu's Balanced Bracket Sequence
1726A - Mainak and Array
1613C - Poisoned Dagger
475B - Strongly Connected City
652B - z-sort
124B - Permutations
1496C - Diamond Miner
680B - Bear and Finding Criminals
1036E - Covered Points
1015D - Walking Between Houses