小红书C++后端开发笔试

编程部分

前面的选择题忘了

T1 零件组装

思路

用桶排思想存一下，然后取最小的零件个数

代码

#include <bits/stdc++.h>
using namespace std;int a[5],cnt[5];int main()
{for(int i = 0;i < 5; ++i) cin>>a[i];int temp;int ans = 0x3f3f3f3f;for(int i = 0;i < 4; ++i) {for(int j = 0;j < a[i]; ++j) {cin>>temp;if(temp >= a[4]) cnt[i]++;}ans = min(ans,cnt[i]);}cout<<ans<<endl;return 0;
}

T2 最佳传送方案

思路

一眼动归，我们定义 f[i] 为到达第 i i i 座山峰的最小花费, a [ i ] a[i] a[i] 为第 i i i 座山峰的高度，很显然能得到状态转移方程：

f [ i ] = { m i n ( f [ j ] , f [ i ] ) , a [ i ] < a [ j ] m i n ( f [ j ] + a [ i ] − a [ j ] , f [ i ] ) , a [ i ] > = a [ j ] f[i] = \begin{cases} min(f[j],f[i]), & a[i]<a[j] \\ min(f[j] + a[i] - a[j],f[i]), & a[i]>=a[j] \end{cases} f[i]={min(f[j],f[i]),min(f[j]+a[i]−a[j],f[i]),​a[i]<a[j]a[i]>=a[j]​

代码

#include <bits/stdc++.h>
using namespace std;const int N = 2000+10;int n,k,a[N];int f[N];int main()
{cin>>n>>k;for(int i = 1;i <= n; ++i) cin>>a[i];memset(f,0x3f,sizeof f);f[0] = f[1] = 0;for(int i = 1;i <= n; ++i) {for(int j = max(1,i - k);j <= i; ++j) {if(a[j] > a[i]) {f[i] = min(f[j],f[i]);} else {int ds = a[i] - a[j];f[i] = min(f[j] + ds,f[i]);}}}cout<<f[n]<<endl;return 0;
}

T3 支配数

思路

开始写了个暴力，直接二重循环匹配过去，发现过了83%，然后突然发现，如果当前的序列中已经满足存在 k k k 个重复数字，那么以当前起点往后的所有序列都能满足支配序列，即 n − r + 1 n-r+1 n−r+1 个序列，那么很显然正解就是双指针，直接扫过去就完事

代码

#include <bits/stdc++.h>
using namespace std;const int N = 100000+10;int n,k,a[N];int f[N];int main()
{cin>>n>>k;for(int i = 1;i <= n; ++i) cin>>a[i];map<int,int> vis;int ans = 0;for(int i = 1;i <= n; ++i) {vis.clear();bool fg = false;for(int j = i;j <= n; ++j) {vis[a[j]]++;if(vis[a[j]] >= k) {ans += (n - j + 1);break;}}}cout<<ans<<endl;return 0;
}