自学内容网 自学内容网
自学内容网 > 正文

小米2025届软件开发工程师(C/C++/Java)（编程题AK）

🕗 发布于 2024-09-26 02:13 c语言  c++  经验分享  动态规划  算法  

选择题好像也是25来个

编程题

T1

题目描述

小明喜欢解决各种数学难题。一天，他遇到了一道有趣的题目:他需要帮助他的朋友们完成一个排序任务。小明得到两个长度为 n 的数组a[]和b[]。他可以在两个数组对应位置进行交换，即选定一个位置 i ，交换a[ i ]和b[ i ]。他可以进行任意次交换(包括0次)，他想知道按最优策略来是否可以达成让至少一个数组a[]或者b[]，变得有序。有序即数组单调不减(升序)或者单调不增(降序)均可。
形式化地，给定两个长度为n的数组a[]和b[]。你可以任选一个位置i交换a[i]和b[i]，可以进行任意多次这样的操作。你的目标是判断是否能够通过这些操作使得至少一个数组变得有序(升序或降序)。小明想要在老师面前证明自己，但这个题目实在有点太难了，请你帮帮他!

输入描述

第一行一个整数T，表示数据组数。
对于每组数据:
第一行包含一个整数n，表示数组的长度。
第二行包含n个整数a1,a2,…,an。
第三行包含n个整数b1,b2.…bn。
1≤T≤100，1≤n≤10000,1≤ai,bi≤10000。

输出描述

输出T行分别表示每组数据答案。
对每组数据，如果能够通过交换操作使至少一个数组变得有序，输出YES;否则，输出NO

样例输入

2
5
1 3 5 2 4
5 2 3 4 1
7
1 2 3 4 3 2 1
4 3 2 1 2 3 4

样例输岀

YES
NO

提示
第一组数据:
在这个样例中，其中一种可行的方法为:通过交换第2、3、4个位置，我们可以使数组 a变成升序:1 2 3 4 4
第二组数据:
无论如何都无法让任何一个数组变得有序。

C++实现代码

#include <bits/stdc++.h>
#include <iostream>
#include <climits>

using namespace std;

int main() {
int T;
int n;
cin >> T;
while (T--) {
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
int t = 0;
// 递增
bool flag1 = true;
for (int i = 0; i < n; i++) {
int tmpmn = min(a[i], b[i]);
int tmpmx = max(a[i], b[i]);
if (tmpmn >= t) {
t = tmpmn;
}
else if (tmpmx >= t) {
t = tmpmx;
}
else {
flag1 = false;
break;
}
}
// 递减
t = 1e9;
bool flag2 = true;
for (int i = 0; i < n; i++) {
int tmpmn = min(a[i], b[i]);
int tmpmx = max(a[i], b[i]);
if (tmpmx <= t) {
t = tmpmx;
}
else if (tmpmn <= t) {
t = tmpmn;
}
else {
flag2 = false;
break;
}
}

if (flag1 || flag2) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}

在这里插入图片描述

T2、装箱

题目描述

小明正在整理他的玩具，他遇到了一道有趣的装箱问题:他有一个容量为 N 的箱子，并且有 n 个大小为a[ i ]的玩具。除了这 n 个玩具外，还有 c 个大小均为1的填充物，它们是小明参加各种活动的纪念品，正好可以拿来填充缝隙。他的任务是确定是否可以选其中一些玩具(填充物也包含在内)放入箱子中，恰好装满箱子，而不留下任何空隙，当然，他也可以选择全部用填充物来填满整个箱子(如果埴充物足够多的话)，也即装满一箱纪念品，小明也觉得很棒!

输入描述

第一行1个整数T，表示数据组数。
对于每组数据:
第一行包含三个整数N和n和c，分别表示箱子的容量和玩具的数量以及填充物数量。
第二行包含n个整数a[1],a[2],…,a[n]，分别表示这n个玩具的大小。
1≤T≤100,1≤n≤500,1≤N,c,a[i]≤1000

输出描述

输出T行分别表示每组数据答案。
对每组数据，输出一行，如果可以恰好装满箱子，输出YES;否则，输出 NO。

样例输入

2
10 4 1
2 3 5 7
10 1 3
6

样例输出

YES
NO

提示
对第一组样例:
箱子的容量是 10，玩具的大小分别为2、3、5和7。
其中一种可行的方法为:玩具 2、3和5 加起来正好是 10，所以可以恰好装满箱子，因此输出 YES。
对第二组样例:
只有一个玩具，大小为6，三个大小为1的填充物，全放进去也只有9的大小，无法填满。

C++实现代码

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int main() {
int T;
cin >> T;
while (T--) {
int N, n, c;
cin >> N >> n >> c;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}

vector<int> dp(N + 1, 0);
for (int i = 0; i < n; i++) {
vector<int> tmp(N + 1, 0);
for (int j = 0; j <= N; j++) {
// 装这个玩具
if (j + v[i] <= N) {
tmp[j + v[i]] = max(tmp[j + v[i]], dp[j] + v[i]);
}
// 不装这个玩具
tmp[max(0, j - v[i])] = max(tmp[max(0, j - v[i])], dp[j]);
}
dp = tmp;
}
int ans = *max_element(dp.begin(), dp.end());
if (ans + c >= N) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}

在这里插入图片描述

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int N, n, c;
        cin >> N>>n>> c;
        vector<int> w;
        for(int i = 0; i < n; i++) {
            int tmp;
            cin>> tmp;
            w.push_back(tmp);
        }
        vector<int> dp(N+1, 0);
        for(int i = 0; i < n; i++) {
            for(int j = N; j >= w[i]; j--) {
                dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
            }
        }
        if(dp[N] + c >= N) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！


原文地址：https://blog.csdn.net/qq_44631615/article/details/142531420

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024