育华周赛 第十九期

j组的同学做前4题

s组的都要做

本期主题 贪心 难度较上期降低

渔船分配 题解

题目分析

这道题要求我们通过最少的移动次数，使得所有渔港的渔船数量都在 $[L, R]$ 范围内。

核心思路

1. 可行性判断：

   • 首先计算总渔船数 $sum$
   • 如果 $n \times L \le sum \le n \times R$，则有解；否则无解，输出 $-1$

2. 贪心策略：

   • 对于渔船数量超过 $R$ 的渔港，需要移出 $a_i - R$ 艘船
   • 对于渔船数量低于 $L$ 的渔港，需要移入 $L - a_i$ 艘船
   • 每次移动可以减少一个渔港的超额数量，同时减少另一个渔港的短缺数量
   • 当需要移出的总船数不等于需要移入的总船数,那么剩余的船只一定有的移出或者移入(通过可行性判断)
   • 最少移动次数 = max(需要移出的总船数,需要移入的总船数)

算法实现

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

const int N = 100;
int a[N];

int main() {
    int n;
    cin >> n;
    
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    int L, R;
    cin >> L >> R;
    
    // 判断是否有解
    if (sum < n * L || sum > n * R) {
        cout << -1 << endl;
        return 0;
    }
    
    //  统计需要移入的船数
    int lans = 0;
    //   统计需要移出的船数
    int rans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > R) {
            rans += a[i] - R;
        }
        if (a[i] < L) {
            lans += L - a[i];
        }
    }
    
    cout << max(lans, rans) << endl;
    return 0;
}

渔船编号优化 题解

题目分析

这道题要求我们在有限的操作次数内，通过加法和减法操作，使得渔船编号尽可能大。

核心思路

1. 贪心策略：

   • 要使编号最大，优先考虑高位先变成最大,依次进行

2. 操作分析：

   • 在同一个位置上不可能加操作和减操作同时进行,于是只要依次进行加和减操作,最多就$2^{17}$种情况

算法实现

方法一：逐位贪心

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

string n;
int A, B;
string ans;


// 递归函数，s为当前字符串，i为当前处理位置，a,b分别为剩余的A和B操作次数
void dfs(string& s, int i, int a, int b) {

    //
    if (i == s.size() || (a == 0 && b == 0)) {
        ans = max(ans, s);
        return;
    }
    // 当前位置是9，直接处理下一位
    if (s[i] == '9') {
        return dfs(s, i + 1, a, b);
    }

    // 剩余A操作次数大于0 则尝试将当前位置的数字加到最大可能
    if (a > 0) {
        int c = min(9 - (s[i] - '0'), a);
        s[i] += c;
        dfs(s, i + 1, a - c, b);
        s[i] -= c;
    }

    // 剩余B操作次数大于0
    if (b > 0) {
        int c = s[i] - '0' + 1;
        if (c > b) {
            // 如果不能减到9,则直接下一步
            dfs(s, i + 1, a, b);
        }else {
            // 如果可以减到9,则尝试减到9
            s[i] = '9';
            dfs(s, i + 1, a, b - c);
            s[i] = '0' + c - 1;
        }
    }
}

int main() {
    cin >> n >> A >> B;
    ans = n;
    dfs(n, 0, A, B);
    cout << ans << endl;

    return 0;
}

渔民组队捕鱼 题解

题目分析

这道题要求我们将 $n$ 个渔民分配到若干艘渔船上，使得每艘船上的渔民人数都满足该船上所有渔民的要求，并最大化渔船数量。

核心思路

1. 问题分析：

   • 每个渔民 $i$ 要求自己所在船上至少有 $a_i$ 个人
   • 如果一艘船上有 $k$ 个渔民，那么这 $k$ 个渔民的 $a_i$ 值都必须 $\le k$
   • 要最大化船的数量，就要让每艘船的人数尽可能少

2. 贪心策略（从大到小）：

   • 如果一艘船上有 $k$ 个渔民，那么这 $k$ 个人的 $a_i$ 最大值必须 $\le k$
   • 从大到小考虑，假设当前渔民的 $a_i = x$，那么船上至少需要 $x$ 个人
   • 我们选择 $a_i$ 最大的前 $x$ 个人放在同一艘船上
   • 由于已经排序，这 $x$ 个人中 $a_i$ 的最大值就是第 1 个人的 $a_i$ 值
   • 只要第 1 个人满足（他的 $a_i \le x$），其他人一定满足

算法实现

方法一：从大到小贪心

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

const int N = 1000010;
int a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 从大到小排序
    sort(a + 1, a + n + 1, greater<int>());
    
    int ans = 0;
    
    for (int i = 1; i <= n; ) {
        // 当前渔民的 a[i] 是最大的，以他为核心组建渔船
        int need = a[i];  // 需要的人数
        
        // 检查是否有足够的人
        if (i + need - 1 > n) {
            // 人数不够，无法继续组队
            break;
        }
        
        // 成功组建一艘船，选择从 i 开始的连续 need 个人
        ans++;
        i += need;  // 跳到下一个未被分配的位置
    }
    
    cout << ans << endl;
    return 0;
}