题目
收到情报，有批新造的机器人要运输到前线。小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
