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