aboutsummaryrefslogtreecommitdiff
path: root/other/reducing_dishes.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/reducing_dishes.cpp')
-rw-r--r--other/reducing_dishes.cpp37
1 files changed, 37 insertions, 0 deletions
diff --git a/other/reducing_dishes.cpp b/other/reducing_dishes.cpp
new file mode 100644
index 0000000..3982095
--- /dev/null
+++ b/other/reducing_dishes.cpp
@@ -0,0 +1,37 @@
+// 1402. Reducing Dishes
+#include "leetcode.h"
+
+/*
+ * a chef has collected data on the 'satisfaction' level of his 'n' dishes. chef
+ * can cook any dish in 1 unit of time. like-time coefficient of a dish is
+ * defined as the time taken to cook that dish including previous dishes
+ * multiplied by its satisfaction level - eg. 'time[i] * satisfaction[i]'.
+ * return maximum sum of like-time coefficient that the chef can obtain after
+ * dishes preparation. dishes can be prepared in any order and the chef can
+ * discard some dishes to get this maximum value.
+ */
+
+class Solution {
+public:
+ int maxSatisfaction(vector<int> &satisfaction) {
+ sort(satisfaction.begin(), satisfaction.end(), greater<int>());
+ int n = satisfaction.size(), pre_sum = 0, ans = 0;
+ for (int i = 0; i < n; i++) {
+ pre_sum += satisfaction[i];
+ if (pre_sum < 0)
+ break;
+ ans += pre_sum;
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> s1 = {-1, -8, 0, 5, -9};
+ vector<int> s2 = {4, 3, 2};
+ vector<int> s3 = {-1, -4, -5};
+ printf("%d\n", obj.maxSatisfaction(s1)); // expect: 14
+ printf("%d\n", obj.maxSatisfaction(s2)); // expect: 20
+ printf("%d\n", obj.maxSatisfaction(s3)); // expect: 0
+}