首页 > 代码库 > NYOJ 678 最小K个数之和

NYOJ 678 最小K个数之和

最小K个数之和

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

输入n个整数,输出其中最小的K个数之和。例如输入4,5,1,1,6,2,7,3,39个数字,当k=4,则输出最小的4个数之和为71,1,2,3)。

输入
测试样例组数不超过10
每个测试案例包括2行:
第一行为2个整数n,k(1<=k<=n<=100000)
第二行包含n个整数,每个整数的范围为【1~2000】
输出
对应每个测试案例,输出最小的k个数之和。
样例输入
8 4
5 2 1 3 8 1 9 3
样例输出
7
AC码:
#include<stdio.h>
int main()
{
	int n,k,i,num[2005],sum=0,a;
	while(~scanf("%d%d",&n,&k))
	{
		for(i=0;i<=2000;i++)
			num[i]=0;
		sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a);
			num[a]++;
		}
		for(i=1;i<=2000;i++)
		{
			if(num[i]==0)
				continue;
			if(num[i]<=k)
			{
				sum+=i*num[i];
				k=k-num[i];
			}
			else
			{
				sum+=k*i;
				break;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}