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;
        else
            return {};
    }   
};

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;
}