Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/
Nội dung bài viết
1. Đề bài PTIT016D spoj
Một dãy gồm n số nguyên không âm a1, a2,…, an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.
Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là biểu thức có giá trị lớn nhất.
Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2,…, an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.
Input
– Dòng đầu chứa hai số nguyên dương n, k (k < n ≤ 105);
– Dòng thứ hai chứa n số nguyên không âm a1, a2,…, an (an ≤ 106)
Output
– Một số nguyên là giá trị của biểu thức đạt được.
Example
Input:
5 2
28 9 5 1 69
Output:
100
2. Code tham khảo PTIT016D spoj PTIT- ACM PTIT 2016
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <iostream> #include <algorithm> #include<functional> using namespace std; #define nmax 100000 long long n, k, a[nmax]; void docfile() { cin >> n>> k; long i; for (i = 0; i < n; i++) cin >> a[i]; } void xuli() { sort(a + 1, a + n, greater<int>()); long i; long long s = 0; for (i = 0; i <= k; i++) s = s + a[i]; for (i = k+1; i <n; i++) s = s - a[i]; cout << s; } int main() { docfile(); xuli(); return 0; } |
Bài viết liên quan
- P151PROG spoj PTIT – Xếp Hàng
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P164SUMI spoj PTIT – ROUND 4I – Next round
- PTIT135J spoj PTIT – Tính lãi suất
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156PROE spoj PTIT – ROUND 6E – Phép dịch
- P156SUMH spoj PTIT – ROUND 6H – Kim cương