Найти наименьшую сумму цен карточек чтобы суммарное время было не меньше за N - C#
Формулировка задачи:
Есть карточки ценой 1, 2, 4, 8, 16 ... на a[0], a[1], a[2] ... a[30] секунд соответственно.
Найти наименьшую сумму цен карточек чтобы суммарное время было не меньше за N.
Пример входных данных
11
1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Пример выходных данных
5
Обьяснение
Мы можем купить карточку с номером 3 по цене 4, тогда времени станет 10,и одну каточку с номером 1 по цене 1, 10+1=11.
Решение задачи: «Найти наименьшую сумму цен карточек чтобы суммарное время было не меньше за N»
textual
Листинг программы
using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication22 { class Program { static void Main() { string a = "11"; string b = "1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"; int intA = int.Parse(a); var intB = b.Split(' ').Select(int.Parse); var result = GetMinSum(intA, intB); Console.WriteLine(result); } private static long GetMinSum(int value, IEnumerable<int> cards) { long sum = 0, k = 1; int currentValue = 0, i = 0; var list = new List<KeyValuePair<int, long>>(); foreach (int card in cards) { if (currentValue > value) break; list.Add(new KeyValuePair<int, long>(card, k)); sum += k; i++; k *= 2; currentValue += card; } if (currentValue < value) throw new Exception("Нельзя составить из данной последовательности"); for (int j = i - 1; j >= 0 && currentValue > value; j--) { if (currentValue - list[j].Key >= value) { currentValue -= list[j].Key; sum -= list[j].Value; } } return sum; } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д