DHEXP spoj – Biểu thức
Nguồn đề bài: http://vn.spoj.com/problems/DHEXP/ 1. Đề thi duyên hải môn tin học khối 10 2015 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. ...
Nguồn đề bài: http://vn.spoj.com/problems/DHEXP/
1. Đề thi duyên hải môn tin học khối 10 2015
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 kdấ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);
– 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
Ghi chú:
- Có 50% số test ứng với 50% số điểm có n ≤ 105 và k = 1;
- Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105;
2. Hướng dẫn DHEXP spoj
– Gợi ý dùng thuật toán tham lam, điền các dấu cộng vào k số lớn nhất. các số còn lại là dấu trừ.
Hướng dẫn cách làm
các bạn có thể dùng Quicksort để sắp xếp. sau đó chọn ra k số để đặt dấu trừ. lưu ý là không đặt dấu cho số đầu tiên.
3. Code tham khảo DHEXP spoj
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | const fi='; nmax=100000; type data=longint; var f:text; A,id:array[0..nmax+1] of data; n,k:data; res:int64; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n,k); res:=0; for i:=1 to n do begin read(f,a[i]); id[i]:=i; res:=res+a[i]; end; close(f); end; procedure swap(var a,b:data); var z:data; begin z:=a; a:=b; b:=z; end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; swap(id[i],id[j]); inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure xuli; var i,j:data; begin sort(1,n); k:=n-1-k; for i:=1 to n do if id[i]<>1 then begin if k=0 then break; res:=res-2*a[i]; dec(k); if k=0 then break; end; writeln(res); end; begin docfile; xuli; end. |
