0 và 1
Xem PDF
Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một mảng gồm \(N\) phần tử \(A[1],A[2],...,A[N]\) với \(A[i]\in \left\{0,1\right\}\text{ }\forall 1\le i\le N\) và ta có một phép toán sau:
- Chọn \(j(1\le j\le n)\) bất kì và gán \(A[j]=1-A[j]\)
Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán để mảng trên chứa các phần tử \(0,1\) xen kẻ nhau.
Input
- Dòng thứ nhất chứa số nguyên \(T(1\le T\le 100)\)- Thể hiện số lượng testcase.
- Ứng với mỗi testcase, sẽ là một block có dạng như sau:
- Dòng thứ nhất chứa số nguyên \(N(1\le N\le 10000)\)
- Dòng thứ hai chứa \(N\) số nguyên \(A[i](1\le i\le n)\) với \(A[i]\in \left\{0,1\right\}\)
Output
- Ứng với mỗi testcase, in ra kết quả cần tìm tương ứng.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(1\le N\le 200\)
- Subtask \(2\) (\(80\%\) số điểm): \(1\le N\le 10000\)
Example
Test 1
Input
3
3
0 0 0
3
0 1 0
3
1 1 1 Output
1
0
1
Bình luận
bài này làm sao vậy mọi người
sẽ tốn 1 bước để từ 1 --> 0 hoặc ngược lại
mình sẽ xét 2 TH là:
• 0 1 0 1 0 ...
• 1 0 1 0 1 ...
kq là min của 2 TH
Cái đó mình xét gì vậy ạ
ví dụ testcase 3 đi: 1 1 1 thì sẽ có 2 TH:
• 1 1 1 --> 1 0 1 tốn 1 bước
• 1 1 1 --> 0 1 0 tốn 2 bước
nên kq là min(1,2) = 1
vậy làm sao để mình kt như thế ạ
duyệt từ đầu tới cuối nếu đúng thì đi tiếp nếu không thì kq++
nhưng 0 1 phải xen kẻ
nếu i chẵn thì là 0 lẻ là 1 còn TH kia thì ngược lại 🙂
em làm y như anh nói mà bị tle
code đâu 🙂
anh tìm n3nhannxt ấy
link
ko thấy 🙂
dạ link đây ạ:
http://lqdoj.edu.vn/submission/121084
đọc kĩ đề đi
họ sẽ cho một dãy gồm các số 0 hoặc 1
từ số 1 muốn chuyển thành số 0 hay ngược lại thì tốn 1 bước
yêu cầu tìm số bước ít nhất để chuyển thành dãy gồm các số 0 và 1 xen kẻ với nhau
thì sẽ có 2 th là:
• 0 1 0 1 …
• 1 0 1 0 …
tức là có 2 th là số 0 trước hoặc là số 1 trước
thì duyệt qua dãy với 2 th và tìm min số bước của 2 th
ví dụ dãy 0 1 1 0 0 1 0
th1: 0 1 1 0 0 1 0 --> 0 1 0 1 0 1 0 thì tốn 2 bước (ở vị trí 3 và 4)
th2: 0 1 1 0 0 1 0 --> 1 0 1 0 1 0 1 thì tốn 5 bước (ở vị trí 1, 2, 5, 6 và 7)
nên kq = min(2, 5) = 2
Dạ rồi ạ.
Em cảm ơn anh @ptk8627
ok bạn
là sao
tức là mình sẽ bày sau UwU
trả lời liên quan vậy