Link Sub: http://www.spoj.com/PTIT/problems/PTIT127E/
Người Gửi: Sai
- Problem:
Trong một lớp có N bàn, mỗi bàn có 2 học sinh. Trong giờ trả bài kiểm tra, mỗi học sinh đều nhận được số điểm kiểm tra của mình. Một đoạn bàn liên tiếp có điểm chung là K, nếu như mỗi bàn trong đoạn bàn đó đều có ít nhất một học sinh có điểm K. Bạn hãy xác định xem đoạn bàn liên tiếp nào có điểm chung với khoảng cách dài nhất.Input
- Dòng 1: Số N (1 ≤ N ≤ 100 000). – là số bàn trong lớp.
- Dòng 2..N+1: Dòng i+1 chứa 2 số nguyên A_i và B_i là điểm kiểm tra của bàn thứ i. (1 ≤ A_i, B_i ≤ 5)
Output
Một dòng chứa 2 số nguyên cách nhau bởi dấu cách: độ dài của đoạn bàn có điểm chung dài nhất và điểm chung K của đoạn bàn đó. Nếu có nhiều đoạn bàn có độ dài dài nhất như nhau, in ra điểm chung K thấp nhất.
Example:
Một dòng chứa 2 số nguyên cách nhau bởi dấu cách: độ dài của đoạn bàn có điểm chung dài nhất và điểm chung K của đoạn bàn đó. Nếu có nhiều đoạn bàn có độ dài dài nhất như nhau, in ra điểm chung K thấp nhất.
Input
1
1 5
Output:
1 1
Input
3
3 5
4 5
1 3
Output:
2 5
Input
4
2 1
3 2
5 3
2 5
Output:
2 2
- Solution:
- Với mỗi số điểm nhập vào sẽ xét thêm các số điểm trước nó. (trừ trường hợp bàn 1).
- Để lưu lại số điểm trước đó ta sẽ dùng mảng đánh dấu lưu lại điểm tại mỗi lần nhập vào.
VD:
Bàn 1: 4 5 -> table[1]: có arrA[4]=1, arrB[5]=1;
Bàn 2: 5 6 -> table[2]: có arrA[5]=1+arrB[5]=2, arrB[6]=1;
....
Cứ như vậy thì mỗi lần ta sẽ có tính được dãy các bàn liên tiếp có cùng điểm.
(Chú ý: vì dãy dài nhất không phụ thuộc vào người 1 có cùng điểm hay người 2 cùng điểm hay thậm chí cả hai cùng điểm vẫn được nên khi xét và cộng thêm số lượng dãy sau thì chỉ cần xét một trường hợp đúng là đủ)Input
3
3 5
4 5
1 3
Output:
2 5
Input
4
2 1
3 2
5 3
2 5
Output:
2 2
- Code:
C++:
https://ideone.com/h3rXZy
#include <iostream>
using namespace std;
int n;
struct data
{
int arrA [10];
int arrB [10];
} typedef data;
data table [100005];
void init ()
{
for (int i=1; i<=n; i++)
{
for (int j=1; j<=5; j++)
{
table[i].arrA[j]=0;
table[i].arrB[j]=0;
}
}
}
int main ()
{
cin>>n;
init ();
int lenMax=0;
int pointMin=10;
for (int i=1; i<=n; i++)
{
int A, B;
cin>>A>>B;
if (i==1)
{
table[i].arrA[A]++;
table[i].arrB[B]++;
if (table[i].arrA[A]>lenMax)
{
lenMax=table[i].arrA[A];
pointMin=A;
}
else if (table[i].arrA[A]==lenMax)
{
if (A<pointMin)
pointMin=A;
}
if (table[i].arrB[B]>lenMax)
{
lenMax=table[i].arrB[B];
pointMin=B;
}
else if (table[i].arrB[B]==lenMax)
{
if (A<pointMin)
pointMin=B;
}
}
else
{
table[i].arrA[A]++;
if (table[i-1].arrA[A]!=0) table[i].arrA[A]+=table[i-1].arrA[A];
else if (table[i-1].arrB[A]!=0) table[i].arrA[A]+=table[i-1].arrB[A];
table[i].arrB[B]++;
if (table[i-1].arrA[B]!=0) table[i].arrB[B]+=table[i-1].arrA[B];
else if (table[i-1].arrB[B]!=0) table[i].arrB[B]+=table[i-1].arrB[B];
if (table[i].arrA[A]>lenMax)
{
lenMax=table[i].arrA[A];
pointMin=A;
}
else if (table[i].arrA[A]==lenMax)
{
if (A<pointMin)
pointMin=A;
}
if (table[i].arrB[B]>lenMax)
{
lenMax=table[i].arrB[B];
pointMin=B;
}
else if (table[i].arrB[B]==lenMax)
{
if (A<pointMin)
pointMin=B;
}
}
}
cout<<lenMax<<" "<<pointMin;
return 0;
}