Đếm số đội trong C ++

Giả sử có n quân nhân đứng thành một hàng. Ở đây mỗi người lính được gán một giá trị xếp hạng duy nhất. Chúng tôi phải tạo một đội gồm 3 người lính trong số họ sử dụng các quy tắc sau -

Chọn 3 lính có chỉ số (i, j, k) sao cho xếp hạng (xếp hạng [i], xếp hạng [j], xếp hạng [k]).

Một đội sẽ hợp lệ nếu - (xếp hạng [i] xếp hạng [j]> xếp hạng [k]).

Chúng tôi phải tìm số đội mà chúng tôi có thể thành lập. (binh lính có thể là một phần của nhiều đội).

Vì vậy, nếu đầu vào giống như xếp hạng =[2,5,3,4,1], thì đầu ra sẽ là 3, vì chúng ta có thể tạo thành ba nhóm như (2,3,4), (5,4,1) , (5,3,1).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=0, n:=kích thước của v
để khởi tạo i:=0, khi i
- để khởi tạo j:=i + 1, khi j
  - để khởi tạo k:=j + 1, khi k
    - nếu v [i]
      - (tăng ret lên 1)
    - ngược lại khi v [i]> v [j] và v [j]> v [k], thì -
      - (tăng ret lên 1)
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numTeams(vector<int>& v) {
      int ret = 0;
      int n = v.size();
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
               if (v[i] < v[j] && v[j] < v[k])
                  ret++;
               else if (v[i] > v[j] && v[j] > v[k])
                  ret++;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,5,3,4,1};
   cout << (ob.numTeams(v));
}

Đầu vào

{2,5,3,4,1}

Đếm số đội trong C ++

Ví dụ

Đầu vào

Đầu ra