智慧杯 考试必备

2019.5. 倒水

描述

Alice 正在家里看电视，突然她听见有人在敲门，她觉得很不开心，竟然有 人来打扰她看电视。开门后她更不开心了，门后竟然站着 K 个老师，这些 老师都是来家访的。Alice 的妈妈看到这么多老师后，赶紧吩咐 Alice 去给 老师们倒水喝。Alice 家里只有一个热水壶，这个热水壶每次最多只能烧开 L 毫升水。 Alice 家里有 N 个杯子，第 i 个杯子的容量为 ai 毫升。Alice 需要从里面选出 K 个杯子给这些老师，然后把每一杯水都倒满，再拿给老 师。Alice 现在想知道，她最少得需要烧多少壶水，才能给这 K 名老师倒够

水。 考虑下面这个例子，N = 4,K = 4,L= 4,1 = 2,= 3,= 1, = 5。 Alice 至少需要烧 3 次水。第一次烧水后，Alice 可以倒满第一，和第三个 杯子。还剩 1 毫升水可以倒到第二个杯子。第二次烧水，Alice 可以倒满第

二个杯子，还剩 2 毫升水可以倒到第四个杯子。最后一次烧开的水可以倒

满第四个杯子。

输入

第一行输入三个整数 N,K,L。接下来一行 N 个整数。第 i 个整数 代表第 i 个杯子的容量

输出

输出一行一个整数代表 Alice 最少需要烧多少次水。

输入样例 1 

4 4 4
2 3 1 5

输出样例 1

3

输入样例 2 

4 3 4
2 3 1 5

输出样例 2

2

提示

题目包含 10 个测试点。

对于第 1,2,3 测试点，满足 N≤20。

对于第 4,5,6 测试点，满足 N≤1000。

对于所有测试点，满足 1≤K≤N≤10^5,1≤,L≤10^9

#include<bits/stdc++.h>
using namespace std;
int arr[10000000];
int main()
{
	int n,k,l;
	cin>>n>>k>>l;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	int sum=0;
	sort(arr+1,arr+n+1);
	for(int i=1;i<=k;i++)
	{
		sum+=arr[i];
	}
	int h,m;
	h=sum/l;
	if(sum%l==0) cout<<h;
	else cout<<h+1;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,k,l;
int a[100005];
int main()
{
    cin>>n>>k>>l;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);//排序
    for(int i=1;i<=k;i++)
        sum+=a[i];//求和
    if(sum%l)cout<<sum/l+1<<endl;//向上取整
    else cout<<sum/l<<endl;
}