STOCK - Thị trường chứng khoán
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, Python, Ruby, Rust, Scratch, Swift
Bạn biết được giá cố phiếu của hãng bất động sản HT trong ~n~ ngày liên tiếp, giá mua và bán trong ngày thứ ~i~ là ~a[i]~ trên một cổ phiếu. Trong một ngày bất kỳ, bạn được quyền lựa chọn một trong các phương án sau:
- Mua 1 cổ phiếu;
- Bán ra một số lượng cổ phiếu nào đó mà bạn có;
- Không mua và bán gì cả.
Yêu cầu: Bạn hãy mua và bán cổ phiếu sao cho lợi nhuận là tối đa?
Input
- Dòng đầu chứa số test ~t\ (1≤t≤10)~. Mỗi test có dạng:
- Dòng đầu tiên chứa số ~n\ (1≤N≤50000)~;
- Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là giá mua và bán cổ phiếu trong ngày ~i\ (1≤a_i≤100000)~.
Output
- Ghi ra một số nguyên duy nhất là lợi nhuận tối đa thu được.
Sample
Input #1
3
3
5 3 2
3
1 2 100
4
1 3 1 2
Output #1
0
197
3
Hint
- Test ~1~: Không mua bán gì cả;
- Test ~2~:
- Ngày ~1~ mua ~1~;
- Ngày ~2~ mua ~1~;
- Ngày ~3~ bán ~2~.
- Test ~3~:
- Ngày ~1~: Mua ~1~;
- Ngày ~2~: bán ~1~;
- Ngày ~3~: Mua ~1~;
- Ngày ~4~: bán ~1~;
Problem source: Chuyên Sơn La Online Judge
Bình luận
Test ví dụ:
Input :
10
1 2 4 9 15 5 8 15 7 9
Output: 63
Ý tưởng:
Bắt đầu từ ngày 1, duyệt đến ngày thứ n, tìm ngày nào bán được nhiều tiền nhất / 1 cổ phiếu (mục đích là để tương ứng với một cổ phiếu mua ở các ngày trước đó, thì chắc chắn bán đi sẽ có lãi)
Gọi đó là ngày thứ "pos", rồi lặp lại tương tự với đoạn [pos + 1, n], cứ thế cho đến khi pos > n thì dừng
Theo ví dụ trên thì sẽ chia được làm 2 đoạn : [1 2 4 9 15 5 8 15] và [7 9] hoặc 3 đoạn : [1 2 4 9 15], [5 8 15] và [7 9]. Nhưng khi các bạn nháp ra thì sẽ thấy 2 cách chia cùng cho ra 1 kết quả
Cách tính sẽ là: (xét cách chia mảng làm 2 đoạn)
Với đoạn 1: tính tổng của số 15 (ở cuối) trừ đi các ngày trước đó -> 61
Với đoạn 2: tính tổng của số 9 (ở cuối) trừ đi các ngày trước đó -> 2
Vậy kết quả sẽ là 61 + 2 = 63. Chúc các bạn AC thành công!!! <3
Code mẫu:
// Solve problem with Justiin
Bài này sẽ sử dụng phương pháp mảng cộng dồn, tham lam để giải quyết nhé mn.
Ta sử dụng hàm void Case() để chia từng test ra và giải quyết từng test đó. Bây giờ ta xét trong 1 test:
Trong một ngày có thể mua hoặc bán hoặc không làm gì cả ( không làm gì thì ta coi là mua 1 cổ phiếu và bán 1 cổ phiếu đó trong ngày luôn ).
Ta sẽ dùng mảng f for từ n về 1 ( f[i] = max( a[i], f[i + 1] ) ) với ý nghĩa là nên bán cổ phiếu vào hôm nào. Vd : như giá cổ phiếu là 1 2 2 5 thì ta sẽ mua cổ phiếu vào ngày 1, 2, 3 và bán hết vào ngày thứ 4 nhưng vd : giá cổ phiếu là 1 5 2 4 thì ta nên mua ngày 1 bán ngày 2 và mua ngày 3 bán ngày 4. Sau đó ta cộng dồn mảng này lại ( i = 1 ... n, f[i] += f[i -1] ) với ý nghĩa là nếu bán cổ phiếu của hôm đó thì được nhiều nhất là bao nhiêu và tổng giá trị nếu bán như thế sẽ được bao nhiêu tính đến ngày i.
Tiếp đến ta dùng một mảng ps để tính tổng giá cổ phiếu từ ngày 1 đến ngày thứ i ( ps[i] = ps[i - 1] + a[i] ) với ý nghĩa là hôm nào cũng mua thì mất bao nhiêu tiền.
Cuối cùng các bạn dùng 1 vòng for ( i = 1 ... n, ans = max( ans, f[n] - f[i - 1] - ( ps[n] - ps[i - 1] ) ). Với ý nghĩa nên bắt đầu tham gia chứng khoán từ hôm nào để có lợi nhiều nhất, f[n] - f[i - 1] là số tiền có lời nhất khi bắt đầu chơi vào ngày i, ps[n] - ps[i - 1] là số tiền bỏ ra để chơi chứng khoán từ ngày i đến ngày n. Và ans là kết quả cần tìm của mỗi test.
// Nếu các bạn thấy có ích thì upvote ủng hộ mình nha.
Code mẫu: