数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究警察用 C++ 抓小偷
在这个问题中，我们给定一个包含 n 个元素的数组。数组的每个元素都包含一个警察或一个小偷，一个小偷可以被一个警察抓住，我们必须找到如果一个警察可以抓住距离他 k 个单位的小偷，那么最多可以抓住多少个小偷。
让我们举个例子来理解这个问题，
输入 −
array = {T, P, P, P, T , T, T}
K = 2.输出 − 3
解释 − 在这里，每个警察都会抓住一个小偷，
P at index 1 will catch T at index 0. P at index 2 will catch T at index 4. P at index 3 will catch T at index 5.
这是允许的，因为警察可以抓住距离他们 2 个单位的小偷。
为了解决这个问题，我们将使用贪心算法。它可以通过两种方式工作，要么抓住离警察最近的所有小偷，要么抓住离警察最远的小偷。但在两种情况下，最优解都没有找到，因为两种情况都存在一些警察必须在一定距离内抓住小偷的情况。
因此，以下是一种提供最有希望结果的算法，
我们将从第一个警察和小偷的索引开始。如果 |index(P1) - index(T1)| <= k，则可以抓住小偷，我们将检查下一对警察-小偷。否则，我们将增加 min(p,t) 并检查警察和小偷的下一个索引。此检查需要一直进行到所有警察和小偷都检查完毕，最后打印被抓获的小偷数量。
示例
程序演示了我们算法的说明，
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int policeThief(char arr[], int n, int k){
int caught = 0;
vector<int> thieves;
vector<int> policemen;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
policemen.push_back(i);
else if (arr[i] == 'T')
thieves.push_back(i);
}
int thief = 0, police = 0;
while (thief < thieves.size() && police < policemen.size()) {
if (abs(thieves[thief] - policemen[police]) <= k) {
caught++;
thief++;
police++;
}
else if (thieves[thief] < policemen[police])
thief++;
else
police++;
}
return caught;
}
int main(){
int k, n;
char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P' };
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Maximum number of thieves that can be caught by police is :"<<policeThief(arr2, n, k);
return 0;
}输出
Maximum number of thieves that can be caught by police is :4
更新于: 2020-04-17
589 次浏览
广告