C++笔试强训day40

本文主要是介绍C++笔试强训day40，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.游游的字母串

2.体育课测验(二)

3.合唱队形

---

1.游游的字母串

链接https://ac.nowcoder.com/acm/problem/255195

英文字母一共就26个，因此可以直接暴力枚举以每个字母作为最后的转变字母。最后去最小值即可

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int main()
{string s;cin >> s;int ret = 1e9;for(char ch = 'a'; ch <= 'z'; ch++){int sum = 0;for(auto x : s){sum += min(abs(x - ch), 26 - abs(x - ch));}ret = min(ret, sum);}cout << ret << endl;return 0;
}

2.体育课测验(二)

链接https://www.nowcoder.com/practice/64a4c026b2aa4411984f560deec36323?tpId=196&tqId=40272&ru=/exam/oj

看描述：

若想完成项目𝑔𝑟𝑜𝑢𝑝𝑠𝑖[0]，必须先完成𝑔𝑟𝑜𝑢𝑝𝑠𝑖[1]

因此可以判断该题为一道拓扑排序题，直接公式化即可完成：

1.建图

2.将入度为0的点加入队列中

3.开始拓扑排序

4.判断是否入度全为0（若不为 0 则可知不可能所有任务都完成）

#include <queue>
#include <unordered_map>
#include <vector>
class Solution {
public:vector<int> findOrder(int numProject, vector<vector<int> >& groups) {int n = numProject;unordered_map<int, vector<int>> edges;vector<int> ret;queue<int> q;int in[2010] = { 0 };        // 建图for(auto e : groups){edges[e[1]].push_back(e[0]);in[e[0]]++;}// 将入度为0的点加入队列中for(int i = 0; i < n; ++i)if(in[i] == 0)q.push(i);// 开始拓扑排序while(q.size()){int t = q.front();q.pop();for(auto e : edges[t]){in[e]--;if(in[e] == 0)q.push(e);}ret.push_back(t);}// 判断是否入度全为0了if(ret.size() == n)return ret;elsereturn {};}   
};

3.合唱队形

链接https://www.nowcoder.com/practice/0045cd3e39634a66ada63c2adeb49234?tpId=230&tqId=39759&ru=/exam/oj

直接去求得最少需要即为同学出列的方法肯定是不可行的。

我们需要换位思考：这个队列最多能有多少人。

因为（1 <= i <= k）

所以该队形可以是这三种情况。

我们可以定一个人为最高点的那个人，然后求得左边的最多人数（x）（呈上升趋势）（包含最高点），再求右边的最多人数（y）（呈下降趋势）（包含最高点），然后我们要求的即为 x + y - 1

所以我们就将题目变相改成求左边的最长上升子序列，右边的最长下降子序列（可以变换为从右向左看求最长上升子序列）

问题就转化为求最长上升子序列了：

即dp问题：

#include <iostream>
using namespace std;
const int N = 1010;int n;
int f[N], g[N], a[N];
int main() {cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i){f[i] = 1;for(int j = 1; j < i; ++j){if(a[i] > a[j])f[i] = max(f[j] + 1, f[i]);            }}for(int i = n; i >= 1; --i){g[i] = 1;for(int j = n; j > i; --j){if(a[i] > a[j])g[i] = max(g[j] + 1, g[i]);            }}int ret = 0;for(int i = 1; i <= n; ++i)ret = max(f[i] + g[i] - 1, ret);cout << n - ret << endl;return 0;
}

这篇关于C++笔试强训day40的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---