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