标签:Target Sum

REPORT-hihoCoder太阁最新面经算法竞赛13(AC #1 #2) – 16.11.3

REPORT-hihoCoder太阁最新面经算法竞赛13(AC #1 #2) – 16.11.3

#1 Inventory is Full
贪心,每个格子优先取最大价值的可放物品,可放物品价值为最大可堆叠数量*单个价值,无法达到最大堆叠数量的或者剩下来的另外作为一个可放物品。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InventoryIsFull
{
    public class Item
    {
        public long Amount { get; set; }
        public long Value { get; set; }
        public long SSize { get; set; }
        public long maxStackCount { get; set; }
        public long StackValue { get; set; }
        public long extraStackValue { get; set; }
        public Item(long A, long V, long S)
        {
            Amount = A;
            Value = V;
            SSize = S;
            maxStackCount = Amount / SSize;
            StackValue = Value * SSize;
            extraStackValue = Value * (Amount - SSize * maxStackCount);
        }
        public Item(long extSV)
        {
            StackValue = extSV;
            maxStackCount = 1;
        }
    }
    public class ItemComparer : IComparer<Item>
    {
        public int Compare(Item x, Item y)
        {
            Item ItemX = x;
            Item ItemY = y;
            if (ItemX.StackValue > ItemY.StackValue)
                return -1;
            if (ItemX.StackValue < ItemY.StackValue)
                return 1;
            return 0;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            string[] inp = Console.ReadLine().Trim().Split(' ');
            int N = Convert.ToInt32(inp[0]);
            int M = Convert.ToInt32(inp[1]);
            List<Item> items = new List<Item>();
            string[] strAmount = Console.ReadLine().Trim().Split(' ');
            string[] strValue = Console.ReadLine().Trim().Split(' ');
            string[] strSize = Console.ReadLine().Trim().Split(' ');
            for (int i = 0; i < M; i++)
            {
                int A = Convert.ToInt32(strAmount[i]);
                int V = Convert.ToInt32(strValue[i]);
                int S = Convert.ToInt32(strSize[i]);
                Item item = new Item(A, V, S);
                items.Add(item);
            }
            for (int i = 0; i < M; i++)
            {
                if (items[i].extraStackValue != 0)
                {
                    Item item = new Item(items[i].extraStackValue);
                    items.Add(item);
                }
            }
            items.Sort(new ItemComparer());
            
            long ans = 0;
            long count = 0;
            int f = 0;
            while (N > count)
            {
                if (items[f].maxStackCount>(N-count))
                {
                    ans += items[f].StackValue * (N - count);
                    break;
                }
                else
                {
                    ans += items[f].StackValue * items[f].maxStackCount;
                    count += items[f].maxStackCount;
                    f++;
                }
            }
            Console.WriteLine(ans);
         }
    }
}

#2 Total Hamming Distance
统计所有二进制每一位的1的个数,这一位对答案的贡献就是C1*(n-C1),然后加起来

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TotalHammingDistance
{
    class Program
    {
        public static void OneCount(long x,long[] M)
        {
            long pos = 0;
            while (x != 0)
            {
                if ((x & 1) == 1) M[pos]++;
                x >>= 1;
                pos++;
            }
        }
        static void Main(string[] args)
        {
            long n;
            n = Convert.ToInt64(Console.ReadLine().Trim());
            long[] k = new long[n];
            string[] inp = Console.ReadLine().Trim().Split(' ');
            for (long i = 0; i < n; i++)
            {
                k[i] = Convert.ToInt64(inp[i]);
            }
            long[] Count1 = new long[128];
            for (long i = 0; i < n; i++)
            {
                OneCount(k[i], Count1);
            }
            long ans = 0;
            for (long i = 0; i < 128; i++)
            {
                ans += Count1[i] * (n - Count1[i]);
            }
            Console.WriteLine(ans);
        }
    }
}

#3 Target Sum