NKTEAM spoj - Team Selection - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/NKTEAM/

1. Đề bài NKTEAM spoj

Các trưởng đoàn đội tuyển tin học vùng Balkan muốn chọn ra những thí sinh mạnh nhất trong khu vực từ N thí sinh (3 ≤ N ≤ 100000). Các trưởng đoàn tổ chức 3 kỳ thi, mỗi thí sinh sẽ tham dự cả 3. Biết rằng không có 2 thí sinh nào có cùng điểm số trong mỗi kỳ thi. Ta nói thí sinh A giỏi hơn thí sinh B nếu A được xếp hạng trước B trong cả 3 kỳ thi. Một thí sinh A được gọi là xuất sắc nếu như không có thí sinh nào giỏi hơn A.

Yêu cầu: Hãy giúp các trưởng đoàn đếm số thí sinh xuất sắc.

Dữ liệu vào

Dòng thứ nhất chứa 1 số nguyên dương N.
3 dòng sau, mỗi dòng chứa N số nguyên dương cách nhau bởi khoảng trắng, là chỉ số của các thí sinh theo thứ tự xếp hạng từ cao đến thấp của kỳ thi tương ứng.

Kết qủa

Gồm 1 số nguyên duy nhất cho biết số thí sinh xuất sắc.

Ví dụ

Dữ liệu mẫu
3
2 3 1
3 1 2
1 2 3

Kết qủa
3

Không có thí sinh nào giỏi hơn thí sinh khác nên cả 3 thí sinh đều xuất sắc.
Dữ liệu mẫu
10
2 5 3 8 10 7 1 6 9 4
1 2 3 4 5 6 7 8 9 10
3 8 7 10 5 4 1 2 6 9

Kết qủa
4

Thí sinh 1, 2, 3, 5 là những thí sinh xuất sắc.

2. Hướng dẫn NKTEAM spoj

Thuật toán:sử dụng BIT.
đầu tiên ta sort tăng dần theo giá trị của a[i];
sau đó với mỗi lần duyêt qua các a[i],ta tìm xem trong các c[i] đã duyệt qua có cặp (b[j],c[j]) nafp mà b[j]<b[i] và c[j]<c[i] k.để là được điều này ta sử dung BIT bằng cách cập nhật min giá trị b[i] vào nút c[i].khi lấy kết quả ta dùng bit tìm giá trị min từ nút c[i] về nút

3. Code tham khảo NKTEAM spoj

//saker1417
#include<bits/stdc++.h>
#define x first
#define y second
#define maxn 100001
using namespace std;
typedef pair < int , int > II;
typedef pair < int , II > III;
III e[maxn];
int n,bit[maxn];
void doc()
{
    cin>>n;
    int p;
    for(int i=1;i<=n;i++) cin>>p,e[p].x=i;
    for(int i=1;i<=n;i++) cin>>p,e[p].y.x=i;
    for(int i=1;i<=n;i++) cin>>p,e[p].y.y=i;
}
void update(int u,int val)
{
    while(u<=n)
    {
        bit[u]=min(bit[u],val);
        u+=u&(-u);
    }
}
int get(int u)
{
    int kq=n+1;
    while(u)
    {
        kq=min(kq,bit[u]);
        u-=u&(-u);
    }
    return kq;
}
void tinh()
{
    for(int i=1;i<=n;i++) bit[i]=n+1;
    sort(e+1,e+n+1);
    int dem=0;
    for(int i=1;i<=n;i++)
    {
        int gt=get(e[i].y.y);
        if(gt>e[i].y.x) dem++;
        update(e[i].y.y,e[i].y.x);
    }
    cout<<dem;
}

int main()
{
    //freopen("NKTEAM.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    doc();
    tinh();
}

0.nếu gtmin<b[i] thì i k phải là xuất sắc,ngược lại i xuất sắc

NKTEAM spoj – Team Selection