贝壳找房2019.8.23开发（超详细的解法！！！）

0x01

解题思路

使用贪心的策略，我们将首先将器材数组从小到大排序，然后一次判断每种器材能不能使用即可，如果发现钱不够了我们取出循环输出结果即可。

n, s = list(map(int, input().split()))
nums = list(map(int, input().split()))
nums.sort()
res = 0
for i in nums:if s > i:s -= ires += 1else:break
print(res)

0x02

解题思路

我们只需要判断字符串的前缀和后缀重复的最大长度是多少即可。例如abaaba，此时aba就是前缀和后缀最长的重叠部分。

abaabaabaaba

我们只要以此作为重叠部分，然后将这些字符串堆叠起来即可。由于数据量较小，我们可以直接暴力枚举。

n, k = list(map(int, input().split()))
s = input()
l = 0
for i in range(1, len(s)):if s[:i] == s[len(s) - i:]:l = i
print(s + s[l:]*(k-1))

0x03

解题思路

按照题目意思来做，每次装价值最大的贝壳，也就是对于输入数据从上向下进行运算即可。

#include <iostream>
using namespace std;int main()
{long long n, m;cin >> n >> m;long long res = 0;for (int i = 0; i < n; ++i) {int x, y;scanf("%d %d", &x, &y);auto t = m / y;if (t > x) {res += x; m -= y * 1ll * x;} else {res += t; m -= y * 1ll * t;}}cout << res << endl;
}

0x04

解题思路

首先不难看出这是一个01背包问题，我们的背包容量就是sum(nums)//2（其中nums表示物品的重量数组）。我们定义 f ( i ) f(i) f(i)表示背包容量是i的时候最少可以装入的物品个数。那么

• f ( i ) = m i n ( f [ i − n u m ] + 1 ) n u m ∈ n u m s f(i)=min(f[i-num]+1) \ num\in nums f(i)=min(f[i−num]+1) num∈nums

其中 n u m num num表示每件物品的重量。接着考虑边界问题，背包初始化的时候默认可以装无穷件物品，对于背包是空的情况单独考虑，此时我们可以容纳0件物品。

最后，当我们算法所有背包容量情况下可以得到的物品个数后，我们还需要从sum(nums)//2 → 0，判断背包中装的物品个数是不是合法，如果是无穷当然就不合法。否则就输出此时的背包容量和背包中装的物品个数即可。

n = int(input())
nums = list(map(int, input().split()))
total = sum(nums)
half = total // 2
mem = [float("inf")] * (half + 1)
mem[0] = 0
for i in range(n):for j in range(half, nums[i]-1, -1):mem[j] = min(mem[j], mem[j - nums[i]] + 1)
for i in range(half, -1, -1):if mem[i] != float("inf"):print(abs(total - 2*i), abs(len(nums) - 2*mem[i]))break

如有问题，希望大家指出！！！

贝壳找房2019.8.23开发（超详细的解法！！！）

0x01

解题思路

使用贪心的策略，我们将首先将器材数组从小到大排序，然后一次判断每种器材能不能使用即可，如果发现钱不够了我们取出循环输出结果即可。

n, s = list(map(int, input().split()))
nums = list(map(int, input().split()))
nums.sort()
res = 0
for i in nums:if s > i:s -= ires += 1else:break
print(res)

0x02

解题思路

我们只需要判断字符串的前缀和后缀重复的最大长度是多少即可。例如abaaba，此时aba就是前缀和后缀最长的重叠部分。

abaabaabaaba

我们只要以此作为重叠部分，然后将这些字符串堆叠起来即可。由于数据量较小，我们可以直接暴力枚举。

n, k = list(map(int, input().split()))
s = input()
l = 0
for i in range(1, len(s)):if s[:i] == s[len(s) - i:]:l = i
print(s + s[l:]*(k-1))

0x03

解题思路

按照题目意思来做，每次装价值最大的贝壳，也就是对于输入数据从上向下进行运算即可。

#include <iostream>
using namespace std;int main()
{long long n, m;cin >> n >> m;long long res = 0;for (int i = 0; i < n; ++i) {int x, y;scanf("%d %d", &x, &y);auto t = m / y;if (t > x) {res += x; m -= y * 1ll * x;} else {res += t; m -= y * 1ll * t;}}cout << res << endl;
}

0x04

解题思路

首先不难看出这是一个01背包问题，我们的背包容量就是sum(nums)//2（其中nums表示物品的重量数组）。我们定义 f ( i ) f(i) f(i)表示背包容量是i的时候最少可以装入的物品个数。那么

• f ( i ) = m i n ( f [ i − n u m ] + 1 ) n u m ∈ n u m s f(i)=min(f[i-num]+1) \ num\in nums f(i)=min(f[i−num]+1) num∈nums

其中 n u m num num表示每件物品的重量。接着考虑边界问题，背包初始化的时候默认可以装无穷件物品，对于背包是空的情况单独考虑，此时我们可以容纳0件物品。

最后，当我们算法所有背包容量情况下可以得到的物品个数后，我们还需要从sum(nums)//2 → 0，判断背包中装的物品个数是不是合法，如果是无穷当然就不合法。否则就输出此时的背包容量和背包中装的物品个数即可。

n = int(input())
nums = list(map(int, input().split()))
total = sum(nums)
half = total // 2
mem = [float("inf")] * (half + 1)
mem[0] = 0
for i in range(n):for j in range(half, nums[i]-1, -1):mem[j] = min(mem[j], mem[j - nums[i]] + 1)
for i in range(half, -1, -1):if mem[i] != float("inf"):print(abs(total - 2*i), abs(len(nums) - 2*mem[i]))break

如有问题，希望大家指出！！！