Hoạt động của chương trình

• Nhập số N
• Nếu N chẵn (N % 2 == 0):
• • Chạy vòng lặp từ 0 → N
  • Mỗi lần lặp thực hiện phép cộng → tổng cộng N + 1 lần
• Nếu N lẻ:
• • Không vào vòng lặp → chỉ in kết quả

Độ phức tạp thời gian

Trường hợp 1: N chẵn

• Vòng lặp chạy N + 1 ≈ N lần
• Mỗi bước là thao tác O(1)

Tổng: O(N)

Trường hợp 2: N lẻ

• Không có vòng lặp
  O(1)

Kết luận chung

• Trường hợp xấu nhất (worst-case): khi N chẵn
  Độ phức tạp: O(N)
• Trung bình / tổng quát:
  vẫn được xem là O(N)

Kết luận cuối:

Độ phức tạp thời gian của chương trình là: O(N)

Ta diễn giải bài toán như sau:

• Có n ngày
• Với mỗi ngày:
• • Máy A có thời gian hoạt động a[i] và thời gian bị tấn công h[i]
  • Máy B có thời gian hoạt động b[i] và thời gian bị tấn công f[i]

Thời gian hoạt động thực mỗi ngày:

\(\left(\right. a \left[\right. i \left]\right. - h \left[\right. i \left]\right. \left.\right) + \left(\right. b \left[\right. i \left]\right. - f \left[\right. i \left]\right. \left.\right)\)

Tổng trong n ngày:

\(\sum \left(\right. a \left[\right. i \left]\right. - h \left[\right. i \left]\right. + b \left[\right. i \left]\right. - f \left[\right. i \left]\right. \left.\right)\)

Áp dụng vào INPUT:

n = 5

• A hoạt động: 20 20 10 21 18
• A bị tấn công: 20 15 11 13 13
• B hoạt động: 23 19 17 22 12
• B bị tấn công: 20 14 11 13 9

Tính từng ngày:

Tổng:

\(3 + 10 + 5 + 17 + 8 = 43\)

Lưu ý:

• Kết quả đề bài cho là 44, nhưng tính đúng theo công thức thì ra 43
• Có thể đề:
• • Sai dữ liệu
  • Hoặc có quy ước không cho phép thời gian âm (ví dụ lấy max(0, a[i]-h[i]))

Nếu sửa theo quy tắc không âm:

Ngày 3: A = max(0, 10 - 11) = 0

Khi đó:

• Ngày 3: 0 + 6 = 6

Tổng mới:

\(3 + 10 + 6 + 17 + 8 = 44\)

Kết luận:

Đáp án đúng: 44 (khi thời gian hoạt động không được âm)

Bước 1 (i = 0):

• Tìm phần tử nhỏ nhất từ vị trí 0 → hết dãy → 1
• Đổi chỗ với vị trí 0 (không đổi)

👉 1, 9, 2, 3, 4, 7, 6, 2

Bước 2 (i = 1):

• Tìm nhỏ nhất từ vị trí 1 → hết → 2
• Đổi chỗ 9 ↔ 2

👉 1, 2, 9, 3, 4, 7, 6, 2

Bước 3 (i = 2):

• Tìm nhỏ nhất từ vị trí 2 → hết → 2
• Đổi chỗ 9 ↔ 2

👉 1, 2, 2, 3, 4, 7, 6, 9

Bước 4 (i = 3):

• Tìm nhỏ nhất từ vị trí 3 → hết → 3
• Không đổi

👉 1, 2, 2, 3, 4, 7, 6, 9

Bước 5 (i = 4):

• Nhỏ nhất là 4
• Không đổi

1, 2, 2, 3, 4, 7, 6, 9

Bước 6 (i = 5):

• Tìm nhỏ nhất từ vị trí 5 → hết → 6
• Đổi chỗ 7 ↔ 6

1, 2, 2, 3, 4, 6, 7, 9

Bước 7 (i = 6):

• Nhỏ nhất là 7
• Không đổi

1, 2, 2, 3, 4, 6, 7, 9