P145PROF spoj PTIT – Quán cà phê
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P145PROF/ 1. Đề bài P145PROF spoj Gia đình Tí mới mở một quán cà phê. Qua thăm dò, Tí đã biết trước ngày khai trường sẽ có n người tới quán trong ngày hôm đó và biết chính xác thời gian người thứ i sẽ tớ vào lúc h[i] giờ, m[i] phút. ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P145PROF/
1. Đề bài P145PROF spoj
Gia đình Tí mới mở một quán cà phê. Qua thăm dò, Tí đã biết trước ngày khai trường sẽ có n người tới quán trong ngày hôm đó và biết chính xác thời gian người thứ i sẽ tớ vào lúc h[i] giờ, m[i] phút.
Quán cà phê mất không quá 1 phút để phục vụ một khách hàng. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.
Ngày khai trương nên gia đình Ti muốn phục vụ được tất cả n người khách. Quán cà phê cần đảm bảo rằng trong mỗi thời điểm số nhân viên phục vụ không ít hơn số lượng khách.
Các bạn hãy giúp Tí biết số nhân viên ít nhất cần có mà vẫn có thể đảm bảo phục vụ trong ngày khai trương.
Input
Dòng đầu tiên ghi số nguyên n ( 1 <=n <= 10^5).
n dòng tiếp theo, mỗi dòng gồm cặp số nguyên h[i], m[i] tương ứng là giờ và phút mà người thứ i tới quán (0 <=h[i]<=23, 0 <= m[i] <= 59).
Output
In ra số nhân viên ít nhất mà vẫn đảm bảo phục vụ được tất cả n người.
Example
Test 1:
Input:
4
8 0
8 10
8 10
8 45
Output:
2
Input:
3
0 12
10 11
22 22
Output:
1
2. Gợi ý P145PROF spoj PTIT
– Đây là dạng bài tập ứng dụng mảng đánh dấu
3. Code tham khảo P145PROF spoj PTIT
a. Code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | CONST fi='; type data=longint; var f:text; A:array[0..23,0..59] of data; max:data=0; n,i:data; u,v:byte; begin assign(f,fi); reset(f); readln(f,n); max:=0; for i:=1 to n do begin readln(f,u,v); inc(a[u,v]); if max<a[u,v] then max:=a[u,v]; end; writeln(max); end. |
b. Code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> #include <algorithm> using namespace std; int a[24][60], n; int main() { int i,j,x,y,res=0; for (i=0; i<=23; i++) for (j=0; j<=59; j++) a[i][j]=0; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d %d",&x,&y); a[x][y]++; res=max(res,a[x][y]); } printf("%d", res); } |
