用 C++ 填充 K 个杯子所需的最小瓶数

问题陈述

给定 N 个盛有水的杯子，以及每个杯子的容量列表。任务是找到填充正好 K 个杯子所需的最小瓶数。每瓶的容量为 100 个单位。

示例

如果 N = 5，K = 4，capacity[] = {1, 2, 3, 2, 1}。

  • 填充容量为 2、3、2 的杯子需要 8 个单位。
  • 这样，只需打开 1 瓶就足够了。

算法

  • 要填充正好 K 个杯子，请取容量最小的 K 个杯子

  • 所需瓶总数可计算为 -

    （前 k 个杯子容量之和）/（每瓶容量）的上限值。

示例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minBottles(int *capacity, int n, int k) {
   sort(capacity, capacity + n);
   int sum = 0;
   for (int i = 0; i < k; ++i) {
      sum += capacity[i];
   }
   return ceil((double)sum/100);
}
int main() {
   int capacity[] = {1, 2, 3, 2, 1};
   cout << "Min bottles required = " <<minBottles(capacity, 5, 4) << endl;
   return 0;
}

输出

编译并执行上述程序时，它会生成以下输出 -

Min bottles required = 1

更新于： 2019-11-22

1K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

开始
广告