Найти наименьшую сумму цен карточек чтобы суммарное время было не меньше за 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;
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4 из 5
Похожие ответы