目錄

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