LABAI - Ghép cặp lá bài
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Tèo có một số lá bài, trong đó có ~A_i~ lá bài ghi giá trị ~i~. Hai lá bài ~x, y~ được gọi là một cặp nếu ~|x − y| ≤ 1~.
Hỏi Tèo có thể tạo tối đa bao nhiêu cặp lá bài biết rằng không có lá bài nào nằm trong ~2~ cặp khác nhau.
Input
- Dòng đầu, chứa số nguyên dương ~N~ ~(1 ≤ N ≤ 10^5)~ là số giá trị khác nhau của các lá bài (các giá trị từ ~1~ đến ~N~);
- ~N~ dòng tiếp theo, mỗi dòng gồm một số nguyên ~A_i~ ~(1 ≤ A_i ≤ 10^9)~.
Output
- Gồm một dòng duy nhất là kết quả bài toán.
Sample
Input #1
4
4
0
3
2
Output #1
4
Hint
- Có ~4~ lá bài ghi số ~1~, ~3~ lá bài ghi số ~2~, ~2~ lá bài ghi số ~4~. Có thể tạo tối đa ~4~ cặp lá bài: ~(1, 1), (1, 1), (3, 4), (3, 4)~.
Problem source: Kc97ble - Free Contest
Bình luận
Ý tưởng của mình là duyệt mảng: i từ đầu đến cuối -XXét: nếu i>1&&i<n thì kiểm tra 2 điều kiện sau : + Nếu a[i]>=1&&a[i-1]%2==1 =>count++,mỗi thằng -1; +Nếu a[i]>=1&&a[i+1]%2==1 =>count++,mỗi thằng -1; --Ra khỏi điều kiện của i thì: +cho count + a[i]/2; =>cập nhật a[i]=a[i]%2; =>AC nhé ae