【招商银行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;
}