PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/ 1. Đề bài PTIT016D spoj Một dãy gồm n số nguyên không âm a 1 , a 2 ,…, a n đượ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 ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/
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; } |
