本文主要是介绍2022牛客寒假算法基础集训营5 C 战棋小孩（逆序对完备证明贪心），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

C 战棋小孩

原题链接

先亮个出题人的题解：

出题人讲的还比较简洁清晰，但我认为证明的最后那里有个小跳步，可能出题人觉得比较显然就没有展开讲吧。首先做一次逆序交换答案会变劣是显然的，然后我们可以得知一个倒序排列的序列可以经过若干次逆序对交换变成这个序列经过全排列后的任何一种情况。那么也就是说任何一种其它的排列都是经过这个倒序的排列经过若干次劣化得来的，所以答案只可能会变劣，因此倒序排列是最优的。

CODE:

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n, k, s, p[N];

int a[30][5], w[30], mx[30][3];

bool cmp(int a, int b) {return a > b;}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> n >> k >> s;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        mx[i][1] = mx[i][2] = -1e9;
        for (int j = 1; j <= 4; ++j) {
            cin >> a[i][j];
            if (j <= 2) mx[i][1] = max(mx[i][1], a[i][j]);
            mx[i][2] = max(mx[i][2], a[i][j]);
        }
    }
    
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        int alll = 0;
        for (int j = 0; j < n; ++j) {
            w[j + 1] = mx[j + 1][1];
            if (((i >> j) & 1)) {
                w[j + 1] = mx[j + 1][2];
                alll++;
            }
        }
        if (alll > k) continue;
        sort(w + 1, w + 1 + n, cmp);
        int cnt = 0;
        w[0] = s;
        for (int j = 1; j <= n; ++j) {
            w[j] += w[j - 1];
            if (w[j] >= p[j]) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

这篇关于2022牛客寒假算法基础集训营5 C 战棋小孩（逆序对完备证明贪心）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！