C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

警官はC++で泥棒を捕まえる

この問題では、n個の要素の配列が与えられます。配列の各要素には警官または泥棒がいます。1人の泥棒は1人の警察に捕まえることができ、警官が彼から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人の距離にいる泥棒を捕まえることができるため許可されています。

この問題を解決するために、欲張りアルゴリズムを使用します。警官に最も近いすべての泥棒を捕まえるか、警官に最も遠い泥棒を捕まえるかの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

  1. Linux上のc++のトップIDEは何ですか？

    大きなプロジェクトは、単なるテキストエディタでは管理が困難です。このような場合にIDEを使用すると、生産性が向上し、フラストレーションが軽減される可能性があります。 IDEにはさまざまな種類があり、ニーズに合ったものを選択する必要があります。 Linuxに最適なC/C++IDEのリストは次のとおりです。 C /C++開発用のNetbeans- Netbeansは、C /C++および他の多くのプログラミング言語向けの無料のオープンソースで人気のあるクロスプラットフォームIDEです。コミュニティで開発されたプラグインを使用して完全に拡張可能です。 Eclipse CDT（C / C ++

  2. Window上のc++のトップIDEは何ですか？

    大きなプロジェクトは、単なるテキストエディタでは管理が困難です。このような場合にIDEを使用すると、生産性が向上し、フラストレーションが軽減される可能性があります。 IDEにはさまざまな種類があり、ニーズに合ったものを選択する必要があります。これがWindowに最適なC/C++IDEのリストです。 Visual Studio − Microsoftが開発したIDEです。このIDEは、Windows上でC ++のプログラムを構築、開発、およびプロファイリングするためのクラス最高のツールを備えています。 Visual Studioには、多数のプラグインを備えた巨大なプラグインストアもありま