程序员进阶之算法练习（五十六）
正文
题目1
题目链接 题目大意： 有一排椅子，总共有n个； 有若干个人坐在上面，我们用数字'0'表示这个位置是空的，'1'表示这个位置已经有人； 人们不想靠的太近，所以不能有两个座位连着坐人； 同时人们也不喜欢浪费，所以希望椅子尽可能多的坐人；
现在已知n个椅子的情况，问这排椅子是否已经坐满？
输入数据： 第一行 𝑛 (1≤𝑛≤1000) 第二行n个数字
输出数据： YES或者NO，表示是否已经坐满。
Examples input 3 101 output Yes input 4 1011 output No
题目解析： 反过来思考，如果椅子没坐满，肯定可以有一个位子可以坐下人，并且仍然满足题目要求。 题目数据量不大，可以枚举每一个为0的位置，将其改为1判断是存在合法数字。
bool check_adjacent(int n) {
for (int i = 1; i < n; ++i) {
if (a[i] == '1' && a[i] == a[i - 1]) {
return true;
}
}
return false;
}
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin >> n;
cin >> a;
if (check_adjacent(n)) {
cout << "No" << endl;
return 0;
}
for (int i = 0; i < n; ++i) {
if (a[i] == '0') {
a[i] = '1';
if (!check_adjacent(n)) {
cout << "No" << endl;
return 0;
}
a[i] = '0';
}
}
cout << "Yes" << endl;
return 0;
}题目2
题目链接 题目大意： 有一辆公共汽车上面有n排座位，每排有两个座位，已知第i排的座位宽度是w[i]； 有2n个乘客会逐个上车，这些乘客会分为两类： 1、性格内向的，会优先选择一排座位都是空的，并且座位宽度最小的一排； 2、性格外向的，会优先选择一排座位不为空的，并且座位宽度最大的一排； 现在想知道这2n个乘客，会分别选中第几排。
输入数据： 第一行 𝑛 (1≤𝑛≤200000) 第二行𝑤1,𝑤2,…,𝑤𝑛 (1≤𝑤𝑖≤1e9) 第三行2n长度的01字符串，1表示乘客是外向的，题目保证外向的乘客上车时，一定能找到一排座位不为空的位置，并且性格外向和性格内向的数量相同。
Examples input 2 3 1 0011 output 2 1 1 2
input 6 10 8 9 11 13 5 010010011101 output 6 6 2 3 3 1 4 4 1 2 5 5
题目解析： 题目的意思比较直接，如果不考虑复杂度，可以直接模拟这个选择的过程，在每个乘客上车的时候，根据类型遍历剩下的位置。这样总体的复杂度是O(N^2)，由于N比较大会超时。 可以知道，性格内向的乘客，永远只会挑选宽度最小的一排，那么可以使用优先队列来处理，把所有排按照宽度排序，每次选择宽度最小的出来，然后从队列剔除，放入另外一个按照宽度从大到小排序的优先队列； 性格外向的乘客，每次都从第二个优先队列选择一个位置宽度最大的即可，题目会保证数据合法。
int n;
cin >> n;
priority_queue<Node> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
q.push(Node(a[i], i));
}
cin >> str;
priority_queue<Node, vector<Node>, cmp> qBig;
for (int i = 0; i < n * 2; ++i) {
if (str[i] == '0') {
Node top = q.top();
q.pop();
cout << top.second << endl;
qBig.push(top);
}
else {
Node top = qBig.top();
qBig.pop();
cout << top.second << endl;
}
}题目3
题目链接 题目大意： 小明电脑上有一个文件，文件名是一串小写字母； 小明很不喜欢'xxx'这个字符串，所以他想对文件名进行修改，去掉某些字符； 问，最少去掉几个字符，文件名会不出现'xxx'。
输入： 第一行n，表示文件名长度；n ( 3 ≤ n ≤ 100 ) 第二行str，表示文件名；
输出： 最少去掉的字符数量。
Examples input 6 xxxiii output 1
样例解释： xxxiii去掉第一个字符'x'，之后剩下xxiii，满足要求，所以最少只需要去掉1个字符。
题目解析： 题目的要求，'xxx'是一个不允许出现的字符串，那么当出现'xxx'的时候就要删除字符； 可以知道，'xxx'不管删除哪一个字符串都是一样的，那么可以这么做： 每次出现'xxx'就删掉一个字符，重新对整个字符串进行检查，直到检查之后没有'xxx'。
思考： 或者'xx...x'的长度是指定长度m呢？（同时1 <= m,n <= 1e5) 那么可以对字符进行聚合，相邻的同样字符进行合并，比如说aabbbc这的字符串就变成(a2,b3,c1)，再对x进行处理；
int n;
cin >> n;
string str;
cin >> str;
int ans = 0;
while (1) {
int ok = 1;
for (int i = 2; i < n; ++i) {
if (str[i] == 'x' && str[i - 1] == str[i] && str[i - 2] == str[i]) {
str.erase(str.begin() + i, str.begin() + i + 1);
ok = 0;
++ans;
break;
}
}
if (ok) {
break;
}
}
cout << ans << endl;题目4
题目链接 题目大意： 有n个节点的树，一共有n-1条边； 去掉最多的边，使得剩下的所有相连节点都是偶数。
输入数据： 第一行 𝑛 (1≤𝑛≤1e5) 接下来n-1条边[𝑢, 𝑣] (1≤𝑢,𝑣≤𝑛)
输出数据： 整数k，表示能去掉的最大边数； 如果无法去掉边满足题目的要求，则输出-1.
Examples input 4 2 4 4 1 3 1 output 1 input 3 1 2 1 3 output -1
题目解析： 对于每个节点u, 假设v1/v2/v3..等是子节点。 对于边（u,v）只有两种可能，cut or retain； 如果包含v集合的节点数是偶数，那么可以cut，并且cut之后也不会影响包含u点集合的节点数； 如果v的节点数是基数，那么只能retian；
遍历树上的节点，记录cut的数量； 最终看root所在集合的节点数量，如果是奇数，无解。
vector<int> g[N];
int vis[N];
int num[N];
int ans;
int dfs(int u) {
int sum = 1;
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!vis[v]) {
dfs(v);
if (num[v] % 2 == 0) {
++ans;
}
else {
sum += num[v];
}
}
}
num[u] = sum;
return sum;
}
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
if (num[1] % 2 == 0) {
cout << ans << endl;
}
else {
cout << -1 << endl;
}
return 0;
}题目5
题目链接 题目大意： 有n个数组，每个数组有m个元素； 对于两个数组可以进行一次合并，新的数组每个index的数字等于原来两个数组对应index 的较大值，比如： 5 0 3 1 2 1 8 9 1 3 =5 8 9 1 3 现在从n个数组中选出2个数组，合并之后得到数组b，并且要求数组b的最小值，要尽可能的大；
输入： 第一行 𝑛 and 𝑚 (1≤𝑛≤3⋅1e5, 1≤𝑚≤8) 接下来n行，每行有m个整数a[i][j]，(0≤𝑎[i][j]≤10^9)
输出： 一行，两个整数x，y，表示第x行和第y行；（x可以等于y）
Example input 6 5 5 0 3 1 2 1 8 9 1 3 1 2 3 4 5 9 1 0 3 7 2 3 0 6 3 6 4 1 7 0 output 1 5
题目解析： 题目的答案具有线性特征：假如最小值x满足要求，那么最小值x+1也满足。 我们对最小值进行二分，先得到mid； 每一行，大于mid的数字可以表示为1，小于mid的数字可以表示为0； 那么数据可以转换为01矩阵： 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 .... 由于m的取值较小，这里最多只有256个数字的可能性； for循环遍历也只需要256^2的复杂度，小于生成这个01矩阵的复杂度，那么check(mid)的代价仍是O(nm)；
那么再乘以二分次数，总体复杂度就是O(logK N M )；
class SolutionA {
int a[N][8];
int n, m;
bool check(int mid, pair<int, int> &ans) {
int index[M];
for (int i = 0; i < M; ++i) {
index[i] = -1;
}
for (int i = 0; i < n; ++i) {
int t = 0;
for (int j = 0; j < m; ++j) {
t <<= 1;
if (a[i][j] >= mid) {
t++;
}
}
index[t] = i;
}
for (int i = 0; i < M; ++i) {
for (int j = i; j < M; ++j) {
if (index[i] == -1 || index[j] == -1) {
continue;
}
int k = i | j;
if (k == ((1 << m) - 1)) {
ans.first = index[i];
ans.second = index[j];
return true;
}
}
}
return false;
}
public:
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
}
}
int l = 0, r = 1e9;
pair<int, int> ans_index;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid, ans_index)) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << ans_index.first + 1 << " " << ans_index.second + 1 << endl;
}
}binary_ans;总结
题目1，简单模拟，题目数据量不大； 题目2，优先队列，优先队列是必备的数据结构； 题目3，暴力求解，在范围不大的情况，不用考虑太复杂，简单有效最重要； 题目4，树形DFS，本质是偶数-偶数=偶数，关键在root节点的逻辑处理； 题目5，典型二分，最小值最大和最大值最小往往有二分的可能；
腾讯云开发者
