题目

收到情报，有批新造的机器人要运输到前线。小C将去破坏机器人的运输。小C将激光炮放置在公路的一旁，等运输车经过的时候发射（假设激光炮一定可以射穿车辆）。由于能源有限，激光炮只能发射两次。可以认为激光炮放在坐标轴的原点处，并向y轴正方向发射。每辆运输车可以看作是一个矩形，起始的x轴坐标为Xi ,所有的车均位于第一象限，长度为Li,速度为1，朝x轴负方向运动。即经过t时间后，该车车头的x坐标为Xi-t，车尾坐标为Xi-t+Li 。只要打中车的任何一个部分就算击中。
请你算算，他在哪两个时刻发射，才能摧毁最多的运输车。

题目描述.png

输入描述

第一行一个正整数 n ( 2≤N≤200 )，表示运输个的数量。
接下来n行，每行两个整数X和L(1≤X、L≤109)，表示一辆车的x轴坐标和长度。

输出描述

输出最多可以摧毁的运输车数量。

输入例子

4
2 2
3 1
5 2

输出例子

4

问题分析

这题基本思想是移动炮台去打车，跟随者一次次提交来理解正确答案的思想吧

第一次提交

想法

先确定车辆的区间范围，然后在那个区间里面找出第一次开炮能够打到的最大车辆数，将这些车辆从车辆列表里一处，然后再找出一次开炮能够打到的最大车辆数，两次相加即为最大摧毁数。

代码

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;
int max_val;

int getMax(vector<int> x_vec, vector<int> l_vec, vector<bool> visit_vec, int n) {
    int max = x_vec[0]+l_vec[0], min = x_vec[0];
    for (int i = 1; i < n; i++) {
        if (x_vec[i] + l_vec[i] >= max) {
            max = x_vec[i] + l_vec[i];
        }
        if (x_vec[i] <= min) {
            min = x_vec[i];
        }
    }

    int lena = max - min + 1;
    int a[lena];
    for (int i = 0; i < lena; i++) {
        a[i] = 0;
        for (int j = 0; j < n; j++) {
            if (visit_vec[j] != true && i + min >= x_vec[j] && i + min <= x_vec[j] + l_vec[j]) {
                a[i]++;
            }
        }

    }
    int max_value = 0;
    int max_index = 0;
    for (int k = 0; k < lena; k++) {
        if (a[k] >= max_value) {
            max_value = a[k];
            max_index = k;
        }
    }

    max_val = max_value;
    return max_index + min;
}

void func(vector<int> x_vec, vector<int> l_vec, int n) {
    vector<bool> visit_vec;
    for (int j = 0; j < n; ++j) {
        visit_vec.push_back(false);

    }

    int max_index = getMax(x_vec, l_vec, visit_vec, n);
    int sum = max_val;

    for (int j = 0; j < n; j++) {
        if (max_index >= x_vec[j] && max_index <= x_vec[j] + l_vec[j]) {
            visit_vec[j] = true;
        }
    }

    getMax(x_vec, l_vec, visit_vec, n);

    cout << max_val + sum << endl;
}

int main() {
    vector<int> x_vec;
    vector<int> l_vec;
    int n, x, speed;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x >> speed;
        x_vec.push_back(x);
        l_vec.push_back(speed);
    }

    func(x_vec, l_vec, n);
    return 0;
}

结果

第一次.png

结果分析

可以看到只能通过89%，咋一看思路很有问题，但是求得的是一个局部最优，并不能代表全局最优，所有下面这种情况会通不过。

第一次失败情况.png

这种情况下，我们的算法只能得到5个，但是最优解是6个

修改思路

枚举所有的两处射击地点。选择摧毁车辆最大数的两处

修改代码如下

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;


void resetVisit(vector<bool> &visit_vec, int n) {
    visit_vec.push_back(false);
    visit_vec.clear();
    for (int i = 0; i < n; ++i) {
        visit_vec.push_back(false);
    }
}

void func(vector<int> start_vec, vector<int> end_vec, int n) {
    int r = end_vec[0], l = start_vec[0];
    for (int i = 1; i < n; i++) {
        if (end_vec[i] >= r) {
            r = end_vec[i];
        }
        if (start_vec[i] <= l) {
            l = start_vec[i];
        }
    }
    vector<bool> visit_vec;
    resetVisit(visit_vec, n);

    int sum = 0;
    for (int i = l; i <= r; i++) {
        int count1 = 0;
        resetVisit(visit_vec, n);

        for (int j = 0; j < n; j++) {
            if (visit_vec[j] != true && i >= start_vec[j] && i <= end_vec[j]) {
                visit_vec[j] = true;
                count1++;
            }
        }

        for (int k = i + 1; k <= r; k++) {
            vector<int> hais_visit;
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (visit_vec[j] != true && k >= start_vec[j] && k <= end_vec[j]) {
                    visit_vec[j] = true;
                    hais_visit.push_back(j);
                    count++;
                }
            }
            for (int m = 0; m < hais_visit.size(); ++m) {
                visit_vec[hais_visit[m]] = false;
            }
            hais_visit.clear();

//            cout << "count1:" << count1 << " count:" << count << endl;
            if (count + count1 > sum) {
                sum = count + count1;
            }
        }
    }

    cout << sum << endl;
}

int main() {
    vector<int> start_vec;
    vector<int> end_vec;
    int n, x, len;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x >> len;
        start_vec.push_back(x);
        end_vec.push_back(x + len);
    }

    func(start_vec, end_vec, n);
    return 0;
}

结果如下

第二次.png

超时了，注意到上面的遍历是按照车辆区间来的，当区间比较大时，时间复杂度会很高，正确思路应该是按照车辆数来遍历

注意了正确答案快要接近了

代码思想

选取两个车辆作为射击点，当其他车辆的车头在选取的车辆车身区间时，该车辆视为可被摧毁。三次循环解决问题

修改之后代码如下

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;


void func(vector<int> start_vec, vector<int> end_vec, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int count = 0;
            for (int k = 0; k < n; k++) {
                if ((start_vec[k] >= start_vec[i] && start_vec[k] <= end_vec[i]) ||
                    (start_vec[k] >= start_vec[j] && start_vec[k] <= end_vec[j])) {
                    count++;
                }
            }

            if (count > sum) {
                sum = count;
            }
        }
    }

    cout << sum << endl;
}

int main() {
    vector<int> start_vec;
    vector<int> end_vec;
    int n, x, len;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x >> len;
        start_vec.push_back(x);
        end_vec.push_back(x + len);
    }

    func(start_vec, end_vec, n);
    return 0;
}

结果

第三次.png

妈卖批，结果有错了
分析一下！！！！

第三次错误情况.png

上面这种情况下，代码算出的是4，实际上是3，从图中可以看出很明显的错误

再次修改代码如下

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;


void func(vector<int> start_vec, vector<int> end_vec, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int count = 0;
            for (int k = 0; k < n; k++) {
                if ((start_vec[i] >= start_vec[k] && start_vec[i] <= end_vec[k]) ||
                    (start_vec[j] >= start_vec[k] && start_vec[j] <= end_vec[k])) {
                    count++;
                }
            }

            if (count > sum) {
                sum = count;
            }
        }
    }

    cout << sum << endl;
}

int main() {
    vector<int> start_vec;
    vector<int> end_vec;
    int n, x, len;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x >> len;
        start_vec.push_back(x);
        end_vec.push_back(x + len);
    }

    func(start_vec, end_vec, n);
    return 0;
}

AC了，哈哈

通过.png