笔试——Day40

第一题

题目

游游的字母串

思路

数据量1e5
枚举所有可能变成的字符情况

代码

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

第二题

题目

体育课测验(二)

思路

拓扑排序

代码

#include <queue>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型vector<vector<>> * @return int整型vector*/vector<int> findOrder(int numProject, vector<vector<int> >& groups) {// write code herevector<vector<int>> edges(numProject); // 边vector<int> in(numProject); // 入度// 建图for(auto & v : groups){int a = v[0], b = v[1];edges[b].push_back(a); // b->ain[a]++;}// 入度0加队列queue<int> q;for(int i = 0; i <numProject; i++){if(in[i] == 0) q.push(i);}// 层序遍历vector<int> res;while(q.size()){int t = q.front(); q.pop();res.push_back(t);for(auto &e : edges[t]){if(--in[e] == 0) q.push(e);}}if(res.size() == numProject)return res;elsereturn {};}
};

第三题

题目

合唱队形

思路

前后分别两次最长上升子序列

代码

#include <iostream>
using namespace std;const int N = 1010;
int a[N];
int n;
int f[N], g[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[j] < a[i]) f[i] = max(f[i], f[j] + 1);}}for(int i = n; i >= 1; i--){g[i] = 1;for(int j = i + 1; j <= n; j++){if(a[j] < a[i]) g[i] = max(g[i], g[j] + 1);}}  int len = 0;for(int i = 1; i <= n; i++){len = max(len, f[i] + g[i] - 1);}cout << n - len << endl;return 0;
}
// 64 位输出请用 printf("%lld")