-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
70 lines (68 loc) · 2.18 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using System;
using System.Collections.Generic;
namespace MaximumProfit
{
class Program
{
static void Main(string[] args)
{
int[] customers = { 10, 10, 6, 4, 7 };
int boardingCost = 1, runningCost = 92;
Console.WriteLine(MinOperationsMaxProfit(customers, boardingCost, runningCost));
}
static int MinOperationsMaxProfit(int[] customers, int boardingCost, int runningCost)
{
int max = 0, profit = 0, left = 0, res = 0;
var groups = new List<int>();
foreach (var customer in customers)
{
int num = Math.Min(customer + left, 4);
groups.Add(num);
left = Math.Max(0, customer + left - 4);
}
while (left - 4 > 0)
{
groups.Add(4);
left -= 4;
}
groups.Add(left);
for (int i = 0; i < groups.Count; i++)
{
profit += groups[i] * boardingCost - runningCost;
if (profit <= max) continue;
max = profit;
res = i + 1;
}
return max == 0 ? -1 : res;
}
static int MinOperationsMaxProfit_O1Space(int[] customers, int boardingCost, int runningCost)
{
int max = 0, profit = 0, left = 0, res = 0, count = 1;
foreach (var customer in customers)
{
profit += Math.Min(customer + left, 4) * boardingCost - runningCost;
if (profit > max)
{
max = profit;
res = count;
}
left = Math.Max(0, customer + left - 4);
count++;
}
while (left - 4 > 0)
{
profit += 4 * boardingCost - runningCost;
if (profit > max)
{
max = profit;
res = count;
}
left -= 4;
count++;
}
if (boardingCost * left - runningCost > 0)
res++;
return max == 0 ? -1 : res;
}
}
}