当前位置: 首页> 文旅> 艺术 > 拼多多20240509实习生笔试

拼多多20240509实习生笔试

时间:2025/8/23 23:17:10来源:https://blog.csdn.net/weixin_61067952/article/details/140241512 浏览次数:0次

题目一

解题思路

分类讨论

情况一:5元汉堡也买不完。

情况二:5元汉堡能买完,非5元买不起。

情况三:都能买起,或还有剩余买原价汉堡。

题目二 

解题思路

找规律,假设有...xy...,x在前。如果交换x、y后,x没有到最右边,且y没有到最左边,那么x、y还是同时作为十位和个位,对结果不影响。

如果y到最左边,会影响个位,比如010变100,结果从11变为10.

如果x到最右边,会影响十位,比如010变001,结果从11变为1.

要想结果最小,先尝试将最右的1移到最右边,再尝试将最左的1移到最左边。

#include <bits/stdc++.h>using namespace std;void solve() {int n, k;cin >> n >> k;string s;cin >> s;int idx0 = s.find('1');int idx1 = s.rfind('1');// Function to perform operation 0auto op0 = [&](int &idx0) {if (idx0 == -1) return;while (k && idx0) {swap(s[idx0], s[idx0 - 1]);k--;idx0--;}};// Function to perform operation 1auto op1 = [&](int &idx1) {if (idx1 == -1) return;while (k && idx1 < n - 1) {swap(s[idx1], s[idx1 + 1]);idx1++;k--;}};if (n - idx1 - 1 <= k)op1(idx1);op0(idx0);int res = 0;for (int i = 0; i < n - 1; i++)res += stoi(s.substr(i, 2));cout << res << "\n";
}int main() {int T;cin >> T;while (T--)solve();return 0;
}

题目三 

解题思路

解法一:暴力。每次遍历得到最长最靠左的子串,然后erase删除。

解法二:

可以维护一个集合,存储当前所有连续相同字符构成的子串的信息(子串长度、左右端点位置)。每次从集合中取出长度最大的子串删除,并更新相邻子串的信息。重复此过程,直到集合为空。时间复杂度为 O(Nlog⁡N)。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;string s;cin >> s;char last = s[0];int cnt = 1, left = 0;map<int, array<int, 3>> mpl, mpr;set<array<int, 3>> se;for (int i = 1; i < n; i++) {if (s[i] != last) {se.insert({-cnt, left, i - 1});mpl[left] = {i - 1, last, cnt};mpr[i - 1] = {left, last, cnt};left = i;cnt = 1;last = s[i];} else {cnt++;}}se.insert({-cnt, left, n - 1});mpl[left] = {n - 1, last, cnt};mpr[n - 1] = {left, last, cnt};int res = 0;while (!se.empty()) {auto fi = *se.begin();auto [cnt, l, r] = fi;char lc = mpr[l - 1][1];char rc = mpl[r + 1][1];if (lc == rc) {int lidx = mpr[l - 1][0];int ridx = mpl[r + 1][0];int lcnt = mpr[l - 1][2];int rcnt = mpl[r + 1][2];se.erase({-lcnt, lidx, l - 1});se.erase({-rcnt, r + 1, ridx});se.insert({-(lcnt + rcnt), lidx, ridx});mpl.erase(r + 1);mpr.erase(l - 1);mpl[lidx] = {ridx, lc};mpr[ridx] = {lidx, lc};}se.erase(fi);mpr.erase(l);mpl.erase(r);if (se.empty()) break;res++;}cout << res << "\n";return 0;
}

题目四 

解题思路

如果暴力枚举,随着枚举的平均值一直增大,能找到满足条件的区间越难。所以会出现true、ture。。。true、false、false这样的非递增序列。既然是有序的,那么就可以用二分法枚举平均值,然后在O(n)的时间复杂度下检测这个平均值是否能满足,如果能,平均值可以继续增大,否则减小。

检测平均值avg是否能满足,从m开始,遍历到n,并且维护一个区间,使得该区间大于等于m且平均值大于等于avg。这可以通过建立一个前缀和(减去平均值,这样只有区间和大于等于0既可满足),记录当前位置i的前m个及以前的最小前缀和,来保持当前区间和最大。

#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;const int MAXN = 100005;
int arr[MAXN];
double sum[MAXN];
int n, m;bool check(double avg) {for (int i = 1; i <= n; ++i) {sum[i] = sum[i - 1] + arr[i] - avg;}double minv = 0;for (int i = m; i <= n; ++i) {minv = min(minv, sum[i - m]);if (sum[i] >= minv) {return true;}}return false;
}int main() {int T;cin >> T;while (T--) {cin >> n >> m;double l = 0, r = 0;for (int i = 1; i <= n; ++i) {cin >> arr[i];r = max(r, (double) arr[i]);}while (r - l > 1e-5) {double mid = (l + r) / 2;if (check(mid)) {l = mid;} else {r = mid;}}printf("%.3f\n", r);}return 0;
}

关键字:拼多多20240509实习生笔试

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: