# 官方题解｜欢乐赛#41

桌子乱的反义词

2025-02-19 17:25:26

发布于：浙江

6阅读

0回复

0点赞

官方题解｜欢乐赛#41

T1.整数部分

题目思路

本题可以利用C++的强制类型转化求浮点数的整数部分。

参考代码

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

int main(){
    double x;
    cin >> x;//先读入浮点数
    cout << (int)x;//用int强制类型转化一下
    return 0;
}

T2.差值最大

题目思路

本题的思路是选出三个数的最大值和最小值，进行做差即可，实现的方法有很多，比如可以三个数轮流比较，也可以进行排序，也可以利用C++STL容器进行求解。

参考代码

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    vector<int>q;//先把所有的数放到一个vector里面
    q.push_back(a);
    q.push_back(b);
    q.push_back(c);
    //利用C++的STL容器中的最大值减去最小值即可
    cout << *max_element(q.begin(), q.end()) - *min_element(q.begin(), q.end());
    return 0;
}

T3.寻找倍数

题目思路

本题主要考查二维数组和双重循环这些语法知识，先开一个二维数组存A数组里面具体的值，然后再对整个数组里面的所有的元素看能不能被 $m$ 整除即可。

参考代码

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

const int N = 1010;
int a[N][N], n, m;

int main(){
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            cin >> a[i][j];
            if(a[i][j] % m == 0) ans ++;
        }
    }
    cout << ans;
    return 0;
}

T4.冒泡排序

题目思路

本题考查冒泡排序的主要思想，冒泡排序的思想是重复地走访过要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。本题要利用 m控制冒泡排序的趟数。

参考代码

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

const int N = 1010;

int a[N], n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    //冒泡排序主要代码
    for(int i = 1; i <= m; i ++ ){//控制排序次数
        for(int j = 1; j <= n - i; j ++ ){
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
            }
        }
    }
    //输出答案
    for(int i = 1; i <= n; i ++ ){
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

T5.最短路径

题目思路

本题是很经典的广搜问题，我们开一个dist数组，dist[i]表示从a到i的最短路径，一开始初始化为无穷大。每个数值只遍历一次，在广搜的时候通过dist[i]的值来判断是否这个点已经搜过。如果通过操作得到的数值是在合法的范围内且没被搜过就把这个数值加入队列，并继续搜，一直搜到 $b$ 为止。

参考代码

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

const int N = 10010;
int dist[N];

void solve(){
    int a, b;
    cin >> a >> b;
    queue<int>q;
    q.push(a);
    //将dist数组初始化为无穷大
    memset(dist, 0x3f, sizeof dist);
    //起点到起点的距离为0
    dist[a] = 0;
    while(q.size()){
        int x = q.front();
        q.pop();
        if(x * 2 <= 10000 && dist[x * 2] > 1e9){//操作1
            dist[x * 2] =  dist[x] + 1;
            q.push(x * 2);
        }
        if(x - 1 >= 0 && dist[x - 1] > 1e9){//操作2
            dist[x - 1] = dist[x] + 1;
            q.push(x - 1);
        }
    }
    cout << dist[b] << endl; 
}
int main(){
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
}

T6.组队问题

题目思路

本题可以直接枚举有多少高手按照「1高手，2菜鸟」的组队方式进行组队，然后可以计算出和这些高手匹配完以后剩下的菜鸟数left，这些菜鸟按照「1菜鸟，2高手的方式组队」，能组队的数目是 $(n - i) / 2$ 和 left 的最小值，其中 $n - i$ 是剩下的高手数目。

参考代码

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

void solve(){
    int n, m;
    cin >> n >> m;
    int ans = 0;
    //team1:1高手2菜鸟，team2:2高手1菜鸟
    for(int i = 0; i <= n; i ++ ){//枚举有多少个高手成为team1的选手
        int cur = i;
        long long left = m - 2ll * i;
        if(left >= 0){//保证剩下的菜鸟数目要大于等于0才合法
            cur += min(1ll * (n - i) / 2, left);
            ans = max(ans, cur);
        }
    }
    cout << ans << endl;    
}

int main(){
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    return 0;
}