Nối dây.

Cho hai đường thẳng song song nằm ngang a và b. Trên mỗi đường thẳng, người ta chọn lấy n điểm phân biệt và gán cho mỗi điểm một số nguyên dương là nhãn của điểm đó. Trên đường thẳng a, điểm thứ i (theo thứ tự từ trái qua phải) được gán nhãn là a_i, trên đường thẳng b, điểm thứ j (Theo thứ tự từ trái qua phải) được gán nhãn là b_j. Ở đây a (a₁, a₂,…,a_n) và b (b₁, b₂,…,b_n) là những hoán vị của dãy số (1, 2,…,n).

Yêu cầu: Hãy chỉ ra một số tối đa các đoạn thẳng thỏa mãn:

+ Mỗi đoạn thẳng phải nối hai điểm có cùng một nhãn, một điểm trên đường thẳng a và một điểm trên đường thẳng b.

+ Các đoạn thẳng đôi một không có điểm chung.

Dữ liệu: Cho trong tệp văn bản LINES.INP gồm:

• Dòng đầu chứa số nguyên dương (n ≤ 10⁵).
• Dòng thứ hai chứa n số theo thứ tự là a₁, a₂,…,a_n.
• Dòng thứ ba chứa n số theo thứ tự là b₁, b₂,…,b_n.

          Kết quả : Ghi ra file văn bản LINES.OUT một số nguyên duy nhất là là số đoạn thẳng nối được.        

Ví dụ:

LINES.INP

                                                             LINES.OUT

 

6

2   3   1   5   6   4

3   2   5   6   1   4                                    4

 

Sau một hồi nghĩ phức tạp thì hoá ra bài này cũng không đến mức phức tạp=)))
Ý tưởng là mình sẽ đưa hai dãy a và b về dạng 1 dãy, VD:

2 3 1 5 6 4
3 2 5 6 1 4
-> 2 3 3 2 1 5 5 6 6 1 4 4

Như trên thì ta sẽ lần lượt đưa các số vào theo thứ tự từ trái sang phải, từ trên xuống dưới (đưa $a[1] = 2$ vào, sau đó đến $b[1] = 3$, tương tự với mọi $1 \leq i \leq N$).

Sau đó chỉ cần đếm số dãy con mà có hai phần tử liên tiếp giống nhau và đó là kết quả.

Hai kí tự liên tiếp giống nhau: 1 là sẽ không cắt nhau với bất kì đoạn nào; 2 là sẽ được cắt bởi 1 hoặc nhiều đoạn lớn hơn khác, mà đương nhiên ta sẽ ưu tiên bỏ đoạn lớn hơn rồi, vậy nên ta giữ lại đoạn bé hơn.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a, b, s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    a.resize(n+1);
    b.resize(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    
    for (int i = 1; i <= n; ++i) {
        s.push_back(a[i]);
        s.push_back(b[i]);
    }
    
    int c = 0;
    for (int i = 0; i < s.size()-1; ++i) {
        if (s[i] == s[i+1]) c++;
    }
    
    cout << c;
    
    return 0;
}