PTIT003 - Khôi phục dãy số
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
Cho 1 hoán vị độ dài ~n~ đuợc miêu tả bởi n số nguyên dương ~p_i~.
Do bất cẩn Bob đã đánh mất hoán vị ban đầu, điều duy nhất Bob nhớ đó là các giá tri ~p_i-p_{i-1} | i=2,3,...n~.
Nhiệm vụ của bạn là giúp Bob tìm ra hoán vị ban đầu.
Input
- Dòng đầu tiên gồm số nguyên duơng n.
- Dòng thứ 2 gồm ~n-1~ số nguyên ~q_i~ miêu tả hiệu 2 số liên tiếp trong hoán vị.
Giới hạn:
- ~1\le n \le 10^5~
- ~1-n \le q_i \le n-1~.
Output
- In ra trên một dòng hoán vị ban đầu. Nếu có nhiều dãy số thỏa mãn, in ra kết quả có tổng các phần tử trong dãy là nhỏ nhất.
- Nếu không tồn tại hoán vị nào thỏa mãn in ra
-1.
Sample
Input #1
3
-2 1
Output #1
3 1 2
Problem source: CLB Lập Trình PTIT
Bình luận
ý tưởng của bài này là từ mảng hiệu D mình sẽ phải suy ra được mảng gốc a[] của nó : a[i]=D[i]+a[i-1] Do không biết được phần tử đầu tiên nên ta có thể duyệt a[0] từ 1->n rồi duyệt từng trường hợp để tìm được mảng nhưng sẽ bị TLE -> Ta nên dùng 1 mảng tổng preFixSum của mảng hiệu : PreFixSum[i]=D[1]+D[2]+..+D[i]=a[1]-a[0]+a[2]-a[1]+..+a[i]-a[i-1]=a[i]-a[0]; Nếu đặt a[0] là x thì a[i]=preFixSum[i]+x , nhưng ta có thể thu hẹp lại khoảng xét x như sau : a[i]>=1 nên a[i]-x >=1-x nên 1-x >= minElement của mảng PreFixSum nên x>=1-minElement , tương tự chặn trên x : x<=n-maxElement(mảng preFixSum) => rồi ta làm các bước còn lại thoyy.