*** CLICK ON ADS **
** BLOOD RELATION WILL BE UPDATED SOON **
PROGRAMMING :
*** CLICK ON ADS **
1.
Problem Statement
You have n barrels lined up in a row, numbered from left to right from one. Initially, the i-th barrel
contains ai liters of water.
You can pour water from one barrel to another. In one act of pouring, you can choose two different
barrels x and y (the x-th barrel shouldn't be empty) and pour any possible amount of water from
barrel x to barrel y (possibly, all water). You may assume that barrels have infinite capacity, so you
can pour any amount of water in each of them.
Calculate the maximum possible difference between the maximum and the minimum amount of
water in the barrels, if you can pour water at most k times.
Input Format
The first line contains one integer t— the number of test cases.
The first line of each test case contains two integers n and k — the number of barrels and the
number of pourings you can make.
The second line contains n integers a1,a2,…,an , where ai is the initial amount of water the i-th barrel
has.
It's guaranteed that the total sum of n over test cases doesn't exceed
Constraints
(1≤t≤1000)
(1≤k
(0≤ai≤10^9)
2⋅(10^5).
Output Format
For each test case, print the maximum possible difference between the maximum and the minimum
amount of water in the barrels, if you can pour water at most k times
PYTHON CODE:
R=lambda:map(int,input().split())
t,=R()
exec(t*'n,k=R();print(sum(sorted(R())[~k:]));')
2.
Problem Statement
One common way of digitalizing sound is to record sound intensity at particular time moments. For
each time moment intensity is recorded as a non-negative integer. Thus we can represent a sound
file as an array of n non-negative integers.
If there are exactly K distinct values in the array, then we need k=⌈logK⌉ bits to store each value. It
then takes nk bits to store the whole file.
To reduce the memory consumption we need to apply some compression. One common way is to
reduce the number of possible intensity values. We choose two integers l≤r, and after that all
intensity values are changed in the following way: if the intensity value is within the range l;r, we
don't change it. If it is less than l, we change it to l; if it is greater than r, we change it to r. You can see
that we lose some low and some high intensities.
Your task is to apply this compression in such a way that the file fits onto a disk of size I bytes, and
the number of changed elements in the array is minimal possible.
We remind you that 1 byte contains 8 bits.
k=⌈logK⌉ is the smallest integer such that K≤2k. In particular, if K=1, then k=0.
Input Format
The first line contains two integers n and I — the length of the array and the size of the disk in bytes,
respectively.
The next line contains n integers ai — the array denoting the sound file.
Constraints
(0≤ai≤10^9) (1≤n≤4⋅10^5, 1≤I≤10^8)
Output Format
Print a single integer — the minimal possible number of changed elements
C ++ CODE:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[400010];
ll n,I;
map<int,int> mp;
ll cnt;
int main(){
scanf("%lld%lld",&n,&I);
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
mp[a[i]]++;
}
sort(a,a+n);
cnt = unique(a,a+n)-a;
if(8*I/n>=19 || (1LL<<(8*I/n))>=cnt){
puts("0");
}else{
ll l = 0,r = cnt-1;
ll m = 1LL<<(8*I/n);
ll sum = 0LL;
for(int i = 0;i<m;i++){
sum+=mp[a[i]];
}
ll res = n-sum;
for(int i = 0;i+m<=cnt;i++){
res = min(res,n-sum);
sum-=mp[a[i]];
sum+=mp[a[i+m]];
}
printf("%lld\n",res);
}
return 0;
}
Post a Comment