用 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+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告