Too_lazy
BAN USER#include <iostream>
using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++) /* To check all possibilities*/
{
int i=n-count;
int minvalue=A[i]; /* min among all values in that subarray*/
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}
#include <iostream>
- Too_lazy August 23, 2018using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++)
{
int i=n-count;
int minvalue=A[i];
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}