【招商银行2020FinTech研发赛道】写了一个简易的题解
自己写了一个简易的题解，不知道是不是正解，大家可以一起来讨论😉
A 金币
经典的数塔问题，自底向上走，可以避免边界条件处理，且结果容易得到
#include <bits/stdc++.h>
using namespace std;
int mmap[1030][1030], dp[1030][1030];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
scanf("%d", &mmap[i][j]);
for(int i = 1; i <= n; ++i)
dp[n][i] = mmap[n][i];
for(int i = n - 1; i >= 1; --i)
for(int j = 1; j <= i; ++j)
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + mmap[i][j];
printf("%d\n", dp[1][1]);
return 0;
}
B 交换座位
遍历，每次处理一对，如果不符合要求就需要进行交换，可以开一个值到下标的映射数组mmap来找到需要的值的位置，维护数组row和mmap即可
#include <bits/stdc++.h>
using namespace std;
int mmap[1030][1030], dp[1030][1030];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
scanf("%d", &mmap[i][j]);
for(int i = 1; i <= n; ++i)
dp[n][i] = mmap[n][i];
for(int i = n - 1; i >= 1; --i)
for(int j = 1; j <= i; ++j)
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + mmap[i][j];
printf("%d\n", dp[1][1]);
return 0;
} C 修塔游戏
- 由于要操作最高和最低，首先进行排序
- k个相同的数必然出现在原数组中，那么可以枚举每一个数
- 对于每一个数要操作后变成k个数，可以只操作左边，只操作右边，或者两边都进行操作，操作次数可以用前缀和简化计算得到，三种情况取最小即可
- 注意到由于每次只能操作最高和最低的塔，可以观察到对于每一个数，操作完成后数组中的元素都会达到相等状态且都比目标值小1，比如 1 2 3 5，对于5，可以如下操作：1 2 3 5 -> 2 2 3 5 -> 2 3 3 5 -> 3 3 3 5 -> 3 3 4 5 -> 3 4 4 5 -> 4 4 4 5，这样如果最终相等的数多于k个，就需要减去多余的元素个数
- 此外，还可以针对已经有k个相同的数进行特判
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200005], presum[200005], cnt[10005];
int main()
{
ll n, k;
scanf("%lld %lld", &n, &k);
for(int i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
++cnt[a[i]];
if(cnt[a[i]] >= k)
{
printf("0\n");
return 0;
}
}
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; ++i)
presum[i] = presum[i-1] + a[i];
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n; ++i)
{
// 左边
if(i >= k)
ans = min(ans, i * a[i] - presum[i] - (i - k));
// 右边
if(n - i + 1 >= k)
ans = min(ans, (presum[n] - presum[i-1]) - (n - i + 1) * a[i] - (n - i + 1 - k));
// 两边一起
ans = min(ans, i * a[i] - presum[i] + (presum[n] - presum[i-1]) - (n - i + 1) * a[i] - (n - k));
}
printf("%lld\n", ans);
return 0;
} 