程序员进阶之算法练习（二）
前言
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接 题目大意：n个点，坐标x[i]从小到大，每个点可以选择Left或者Right的方向前进，速度v=1，求相遇的时间。 代码实现：
int right = -1;
for (int i = 0; i < n; ++i) {
if (str[i] == 'R') {
right = i;
}
else {
if (right != -1 && a[i] != a[right]) {
if (ret == -1) {
ret = (a[i] - a[right]) / 2;
}
else {
ret = min(ret, (a[i] - a[right]) / 2);
}
}
}
}题目解析： 对于点i，有两种碰撞情况： 1、方向是L，遇到左边的点方向是R； 2、方向是R，遇到右边的店方向是L； 假设点i和点j是碰撞的点，那么点i的情况1就是点j的情况2； 那么对于点i只考虑左边的点即可； 题目变成：对于每个点，求左边最近的方向为R 的点。
B
题目链接 题目大意：n*m的棋盘上有若干点，找一个点横竖能覆盖所有点。
方法1：
代码实现：
// 假设符合的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
Node tmp;
tmp.x = i;
tmp.y = j;
nodes.insert(tmp);
}
}
// 检查假设的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
if (str[i][j] == '*') {
set<Node>::iterator it = nodes.begin();
while (it != nodes.end()) {
if (it->x == i || it->y == j) {
++it;
}
else {
nodes.erase(it++);
}
}
if (nodes.size() == 0) {
OK = 0;
}
}
}
}题目解析： 假设所有点符合，用set来存放所有的点，每遇到一个点，把不符合的去掉； 时间复杂度为O(NM*LogN)，复杂度的关键在于set的构建。
方法2：
代码实现：
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>c[i][j];
if(c[i][j]=='*'){
k++;
a[i]++;
b[j]++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++) {
s=a[i]+b[j];
if(c[i][j]=='*'){
s--;
}
if(s==k) {
cout<<"YES"<<endl<<i+1<<" "<<j+1;
return 0;
}
}
}题目解析： 假设某一点符合，求这一个点覆盖的点数是否包括其他所有需要覆盖的点； 事先统计每行每列对应的点数，求点覆盖点数时通过每行每列的值可以较快计算出来。 时间复杂度为O(NM)。
C
题目链接 题目大意：有n天，每天有四种可能，如下。问最少能休息几天。 1、on this day the gym is closed and the contest is not carried out; 2、on this day the gym is closed and the contest is carried out; 3、on this day the gym is open and the contest is not carried out; 4、on this day the gym is open and the contest is carried out. 不能连续两天比赛，也不能连续两天锻炼。
代码实现：
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
d[i][0] = min(min(d[i - 1][0] + 1, d[i - 1][1] + 1), d[i - 1][2] + 1);
if (k == 0) {
d[i][1] = d[i][2] = N;
}
if (k == 1) { // can to contest
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = N;
}
if (k == 2) { // can to gym
d[i][1] = N;
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
if (k == 3) {
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
}
cout << min(min(d[n][0], d[n][1]), d[n][2]) << endl;题目解析： 典型的动态规划。 d[i][j]表示第i天，状态为j时的最小休息天数。 j = 0表示都不去； j = 1表示去contest； j = 2表示去gym；
这样j = 0可以由前面三种状态转换过来； j = 1只能由0和2转换； j = 2只能由1和2转换；
然后动态规划一遍得最优解。
D
题目链接 题目大意：n个点，每个点对应的a[i]表示第i个点的parent节点，问使其变成一棵树，最少需要修改多少条边，并且把所有值输出。 代码实现：
lld find(lld x) {
lld ret = f[x];
if (ret != x) {
ret = find(ret);
}
return f[x] = ret;
}
int main() {
for (int i = 1; i <= n; ++i) {
if (i != root) {
lld x = find(i);
lld y = find(a[i]);
if (x == y) {
++ans;
if (!root) {
root = x;
}
a[i] = root;
}
else {
f[x] = f[y];
}
}
}
}题目解析： n个点，n条边。如果是树必然是一条边指向自己，其余n-1条边没有环。（有且仅有一个环） 那么假设有一个根节点root，当出现环的时候，直接将环某个点指向root即可； 需要修改的数量=环的数量 - 1。
总结
两个关键词：动态规划（C题）、并查集（D题）。
腾讯云开发者
