Codeforces Round #792 (Div. 1 + Div. 2) // C ~ E

Codeforces Round #792 (Div. 1 + Div. 2)：C ~ E，构造，贪心

比赛链接：Dashboard - Codeforces Round #792 (Div. 1 + Div. 2) - Codeforces

 

C. Column Swapping

题意：

给定一个n*m大小的二维数组，要求只进行一次两列交换，使得得到的新数组的每行都是不减的。特别的，允许交换的两列是相同列。

思路：构造

可以考虑复制一份数组，并将其排序，那么两个数组中出现数字大小不同的列就是需要进行交换的列。

设需要交换的列的数量为num：

◇ 当num=0，无需交换，可以直接选择交换1 1。
◇ 当num=2时，尝试交换两列，并判断交换后，每行的这两列位置的数字是否已与排序后的该位置的数字相等。
◇ 当num>2时，那么需要交换的次数是大于1的，故无法满足要求。

参考代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200010;

int n, m;
vector<int> v[N], nv[N];

bool check(int c1, int c2)
{
    for(int i = 0; i < n; i++)
        if(v[i][c1] != nv[i][c2] || v[i][c2] != nv[i][c1]) return false;
    return true;
}

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) v[i].clear();
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int x;
            scanf("%d", &x);
            v[i].push_back(x);
        }
        nv[i] = v[i];
        sort(nv[i].begin(), nv[i].end());
    }

    int pos1 = -1, pos2 = -1;
    bool ok = true;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(v[i][j] != nv[i][j]) {
                if(pos1 == -1 || pos1 == j) pos1 = j;
                else if(pos2 == -1 || pos2 == j) pos2 = j;
                else ok = false;
            }
        }
    }

    if(!ok) puts("-1");
    else {
        if(pos1 == -1 && pos2 == -1) puts("1 1");
        else if(check(pos1, pos2)) printf("%d %d\n", pos1 + 1, pos2 + 1);
        else puts("-1");
    }
}

int main()
{
    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}

 

D. Traps

题意：

给定一个大小为n的数组a[]为基础花费，以及最大跳过次数k：每次跳过可直接越过一格，但同时，后续走的每一格都增加1的附加花费。当从 i-1 走到 i 且已进行 cnt 次跳过操作时，此次花费为a_i + cnt。求从0走到n所需的最小花费。

思路：贪心 构造

取 a_i + i 最大的 min(n, k) 个格子跳过，然后模拟一下求总花费即可。

证明：

 ☆ 跳过次数应为min(n,k)：

　　假设当前跳过次数为K，且仍有可跳过的格子且还有跳过次数，那么考虑跳过最后一个未跳过的格子，最终的花费必定只减不增。因此，跳过次数越多，结果越优。

 ☆ 取 a_i + i 较大的格子跳过：

　　假设有a_x + x > a_y + y，若只跳过x和y其中某一格，有两种情况，其中二者出现差异的部分仅在区间 [x，y]内，若假设此前跳过了cnt步，则有：

　　① 跳过x：cost1 = sum[x + 1，y] + (cnt + 1) * (y - x).

　　② 跳过y：cost2 = sum[x，y - 1] + cnt * (y - x).

　　进而，cost1 - cost2 = a_y - a_x + y - x = a_y + y - (a_x + x) < 0 ，即跳过x的花费比跳过y更小。

　　因此，应考虑优先跳过 a_i + i 较大的格子。

参考代码：

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
using namespace std;

const int N = 200010;

int n, k, a[N], id[N];
PII p[N];

void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p[i] = { a[i] + i, i };
    }
    sort(p + 1, p + 1 + n, greater<PII>());
    for(int i = 1; i <= n && i <= k; i++) id[i] = p[i].second;
    sort(id + 1, id + 1 + min(n, k));
    
    int cnt = 0;
    LL res = 0;
    for(int i = 1; i <= n; i++) {
        if(cnt < k && i == id[cnt + 1]) ++ cnt;
        else res += a[i] + cnt;
    }
    cout << res << endl;
}

int main()
{
    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}

 

E. MEX vs DIFF

题意：

给一个大小为n的非负数组a，以及k次操作，每次操作可以将a中任意一个数变成任意数。

有mex为不包含与a中的最小的非负整数，dif为a中不同数的数量，求dif - mex的最小值。

思路：贪心 构造

可以发现dif必然不小于mex，dif - mex的值实际上等于：大于mex的不同数的个数。所以最终答案应该令mex尽量大，同时，让大于mex的不同数的个数尽量小。

❤ 令mex尽量大：先求mex的最大值。

❤ 令大于mex的不同数的个数尽量小：muitiset维护一下，让大于mex的数中，数量较少的数优先进行改变操作。

参考代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, k, a[N];
map<int,int> num, dnum;

void solve()
{
    num.clear();
    cin >> n >> k;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), ++ num[a[i]];
    dnum = num;

    // 求mex最大值
    sort(a + 1, a + 1 + n);
    int mex = 0;
    while(num[mex]) ++ mex;
    for(int i = n, j = k; i && j; i--, j--) {
        if(a[i] < mex) break;
        num[mex] = 1, -- num[a[i]];
        while(num[mex]) ++ mex;
    }

    // 求mex最大时，dif最小值
    multiset<int> S;
    for(auto i : dnum) {
        if(i.first > mex) S.insert(i.second);
    }
    int dif = mex;
    for(auto i : S) {
        if(k >= i) k -= i;
        else ++ dif;
    }

    cout << dif - mex << endl;
}

int main()
{
    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}